Cycle

Ery is interested in graph theory, today he ask BrotherK a problem about it: Given you a undirected graph with $N$ vertexes and $M$ edges, you can select a vertex as your starting point, then you need to walk in the graph along edges. However, you can't pass a edge more than once, even opposite direction is forbidden. At the end, you should come back to the starting point. Assume you has passed $X$ edges, there are two questions:

Question 1: Can $X$ be a odd number ?

Question 2: Can $X$ be a even number ?

(note: you must walk, so $X$ can't be 0)

The first line contains a single integer $T$, indicating the number of test cases.

Each test case begins with two integer $N,~M$, indicating the number of vertexes and the number of edges. Following $M$ lines, each line contains two integers $U_i,~V_i$, indicating there are a edge between vertex $U_i$ and vertex $V_i$.

$T$ is about 30

$1~\le~N~\le~100000$

$0~\le~M~\le~300000$

$1~\le~U_i, V_i~\le~N$

$U_i$ will not equal to $V_i$

There is at most one edge between any pair of vertex.

For each test, print two lines.

The first line contains "YES" or "NO" for question 1.

The second line contains "YES" or "NO" for question 2.

3
1 0
3 3
1 2
2 3
3 1
4 4
1 2
2 3
3 4
4 1

NO
NO
YES
NO
NO
YES

If you need a larger stack size,
please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.

赛码"BestCoder"杯中国大学生程序设计冠军赛