2021 年东华大学金马程序设计联赛

C. Back
PDF 题面可用

There are $N$ villages and $M$ roads. If there is a road between two villages, they are directly reachable. If two villages are not directly reachable, they can first go to other directly reachable villages and then reach each other. We guarantee that there is at most one road between two villages, and each road is two-way, and any two villages can be reached. SDZ likes walking after dinner, but he doesn’t like to walk twice on the same road. He wondered whether there was a route, and he set off along this route, and eventually he could return to the starting point without the road being repeated.

输入格式

There are two numbers $N$ and $M$ in the first line, which means there are $N$ villages and $M$ roads.($1\leq N\leq 1000,1\leq M\leq \frac{N\times (N-1)}{2}$)

In the next $M$ line, each line has two numbers $u$, and $v$ indicates that there is a road between village $u$ and village $v$.

Note that there are multiple sets of inputs and the sum of $N$ is not more than $5000$ and the sum of $M$ is not more than $1000000$.

输出格式

If such a route can be found, output Yes, otherwise output No.

样例

Input
1 1
1 1

Output
Yes


NaN