Cycle

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

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)

Input

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.

Output

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.

Sample Input

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

Sample Output

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

Hint

hujie

Source

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

提交代码