F. Edge Three-Coloring
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an undirected connected graph with $$$n$$$ vertices and $$$m$$$ edges, where $$$m \le n + 9$$$.

Each edge of the graph must be colored with one of three colors numbered from $$$1$$$ to $$$3$$$. We say that vertices $$$u$$$ and $$$v$$$ are reachable in color $$$c$$$ if there exists a path from $$$u$$$ to $$$v$$$ consisting only of edges of color $$$c$$$.

Determine whether there exists a way to color the edges such that the following conditions are satisfied:

  • for each color, there is at least one edge painted in that color;
  • for every pair of colors $$$i$$$ and $$$j$$$ and every pair of vertices $$$u$$$ and $$$v$$$, the following holds: if $$$u$$$ and $$$v$$$ are reachable in color $$$i$$$ and $$$i \lt j$$$, then they are also reachable in color $$$j$$$.
Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case begins with a line that contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 3000$$$; $$$n - 1 \le m \le n + 9$$$) — the number of vertices and edges in the graph.

Each of the next $$$m$$$ lines of a test case contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — the endpoints of the $$$i$$$-th edge.

Additional constraints on the input:

  • the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$;
  • in each test case, the graph has no self-loops or multiple edges;
  • in each test case, the graph is connected.
Output

For each test case, print the answer as follows: if such an edge coloring exists, print YES; otherwise, print NO. Each letter may be printed in any case.

Example
Input
4
4 6
1 2
2 3
3 1
1 4
2 4
3 4
3 3
1 2
2 3
3 1
7 9
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 1
5 8
1 2
2 3
3 4
4 1
5 1
5 2
5 3
5 4
Output
YES
NO
NO
YES
Note

In the first example, it's possible to paint the $$$5$$$-th edge in color $$$1$$$, the $$$1$$$-st and the $$$4$$$-th edge in color $$$2$$$, and all other edges in color $$$3$$$.