Determining Bipartiteness of Graphs

Given an undirected graph, determine whether it is bipartite. A graph is bipartite if its vertices can be colored using two colors such that no two adjacent vertices share the same color. Equivalently, a graph is bipartite if and only if it does not contain an odd cycle.

More formally, for a graph with V vertices and E edges, you are to decide if there exists a partition of the vertex set into two disjoint subsets such that for every edge \( (u,v) \), \( u \) and \( v \) are in different subsets.

Note: The graph may be disconnected. In such cases, you need to check each connected component separately.

inputFormat

The input is read from standard input and has the following format:

T
V1 E1
u1 v1
...
uE1 vE1
V2 E2
... (edges for test case 2)
...
VT ET
... (edges for test case T)

Here, T is the number of test cases. For each test case, the first line contains two integers \( V \) (the number of vertices) and \( E \) (the number of edges). The following E lines each contain two integers \( u \) and \( v \) indicating that there is an edge between vertices u and v.

outputFormat

For each test case, output a single line to standard output containing either Yes if the graph is bipartite, or No otherwise.

## sample

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

No
Yes

</p>