2017-11-04 08:55

# Cycle

Problem 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 Ui, Vi, indicating there are a edge between vertex Ui and vertex Vi.

1 ≤ N ≤ 100000

0 ≤ M ≤ 300000

1 ≤ Ui,Vi ≤ N

Ui will not equal to Vi

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

• 点赞
• 写回答
• 关注问题
• 收藏
• 邀请回答