Under construction

Still being built. Things may change

Bipartite Graph

Interview

Time limit2sMemory limit256 MB

Summary
For several undirected graphs, determine whether each one can be 2-colored so that no edge joins two vertices of the same color.
Level

Medium4 of 10

Topics
Graph, BFS, DFS
Solved
No attempts yet

Problem

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.

Input

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.

Output

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

Constraints

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

Examples1

  1. Example 1

    Input
    2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2
    Expected output
    YES
NO