/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
高橋君は木の問題が苦手です。そこで、青木君は高橋君の練習相手になってあげることにしました。
まず、高橋君は N 頂点からなる木を用意し、頂点に 1 から N の番号を付けました。 そして、各辺に 0 と書きました。
次に、青木君は高橋君に M 個のクエリを与えました。i 個目のクエリは以下のような内容です。
- 頂点 a_i と頂点 b_i を結ぶパス上の辺すべてに対して、書かれている数を 1 増やす。
全てのクエリを終えた後、高橋君は青木君にどの辺を見ても書かれている数が偶数になったと伝えました。 しかし、青木君は最初に高橋君が用意していた木を確認していなかったので、 高橋君が正しくクエリを処理できたか分かりませんでした。
青木君を助けるために、高橋くんの言う性質を満たす木が存在するかどうかを判定してください。
制約
- 2 ≦ N ≦ 10^5
- 1 ≦ M ≦ 10^5
- 1 ≦ a_i,b_i ≦ N
- a_i ≠ b_i
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 : a_M b_M
出力
高橋くんの言う性質を満たす木が存在するならば YES を、存在しないならば NO を出力せよ。
入力例 1
4 4 1 2 2 4 1 3 3 4
出力例 1
YES
例えば、頂点 1 と頂点 2,3,4 が辺で結ばれているような木を高橋君が持っている場合は、高橋くんの言っていることは正しいです。 この場合、クエリをすべて終えた後各辺に書かれている数はどれも 2 になります。
入力例 2
5 5 1 2 3 5 5 1 3 4 2 3
出力例 2
NO
Score : 500 points
Problem Statement
Takahashi is not good at problems about trees in programming contests, and Aoki is helping him practice.
First, Takahashi created a tree with N vertices numbered 1 through N, and wrote 0 at each edge.
Then, Aoki gave him M queries. The i-th of them is as follows:
- Increment the number written at each edge along the path connecting vertices a_i and b_i, by one.
After Takahashi executed all of the queries, he told Aoki that, for every edge, the written number became an even number. However, Aoki forgot to confirm that the graph Takahashi created was actually a tree, and it is possible that Takahashi made a mistake in creating a tree or executing queries.
Determine whether there exists a tree that has the property mentioned by Takahashi.
Constraints
- 2 ≤ N ≤ 10^5
- 1 ≤ M ≤ 10^5
- 1 ≤ a_i,b_i ≤ N
- a_i ≠ b_i
Input
Input is given from Standard Input in the following format:
N M a_1 b_1 : a_M b_M
Output
Print YES if there exists a tree that has the property mentioned by Takahashi; print NO otherwise.
Sample Input 1
4 4 1 2 2 4 1 3 3 4
Sample Output 1
YES
For example, Takahashi's graph has the property mentioned by him if it has the following edges: 1-2, 1-3 and 1-4. In this case, the number written at every edge will become 2.
Sample Input 2
5 5 1 2 3 5 5 1 3 4 2 3
Sample Output 2
NO