Unplanned Queries

AtCoder

IDagc014_b

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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$.

Input #2

Output #2

NO

API Response (JSON)

{
  "problem": {
    "name": "Unplanned Queries",
    "description": {
      "content": "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 ea",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc014_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Takahashi is not good at problems about trees in programming contests, and Aoki is helping him practice.\nFirst, Takahashi created a tree with $N$ vertices numbered $1$ through $N$, and wrote $0$ at ea...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments