Bipartite Graph

An undirected graph is bipartite if its vertices can be divided into two groups so that no edge connects two vertices in the same group.

You are given several graphs. Determine whether each graph is bipartite.

The first line contains the number of test cases K.

For each test case, the first line contains the number of vertices V and the number of edges E, separated by a space. The vertices are numbered from 1 to V.

The next E lines each contain two adjacent vertices u and v, separated by a space. The two vertices are distinct.

For each test case, print YES if the graph is bipartite, or NO otherwise, one answer per line.

• 2 <= K <= 5
• 1 <= V <= 20,000
• 1 <= E <= 200,000