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)

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.

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.

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

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

提交代码