pupil likes to color the vertices of a graph. One day, master wanted to challenge him, so he provided an undirected graph with no multiple edges or self-loops, and assigned a set of 2 colors to each vertex. pupil must choose exactly one color from the assigned set for each vertex. master wants pupil's coloring scheme to ensure that no two adjacent vertices are colored with the same color.

Now, pupil wants to know whether he can always satisfy the requirement, regardless of what the color sets assigned by master are.

Input

The input contains multiple test cases. The first line contains a single positive integer $T$, representing the number of test cases. For each test case, the first line contains two space-separated integers $n$ and $m$, representing the number of vertices and edges in the undirected graph. The following $m$ lines each contain two space-separated positive integers $i$ and $j$, representing an edge between vertex $i$ and vertex $j$ in the graph. The vertices of the graph are labeled starting from 1.

Output

For each test case, if pupil can always color the graph as required, output a single line containing the string YES. Otherwise, output a single line containing the string NO.

Examples

Input 1

3
6 9
1 2
1 4
1 6
3 2
3 4
3 6
5 2
5 4
5 6
2 1
1 2
3 3
1 2
1 3
2 3

Output 1

NO
YES
NO

Note

For the first test case, if the sets for the first and second vertices are $\{A, B\}$, the sets for the third and fourth vertices are $\{A, C\}$, and the sets for the fifth and sixth vertices are $\{B, C\}$, then the odd-indexed vertices use at least two colors, and the even-indexed vertices use at least two colors. Therefore, at least one odd-indexed vertex and one even-indexed vertex will have the same color. However, there are edges between every pair of odd-indexed vertices and every pair of even-indexed vertices, so it is impossible to satisfy the condition that "no two adjacent vertices are colored with the same color."

For the second test case, regardless of what the two sets are, the first vertex can be colored with one of the colors in its set, and the second vertex can be colored with a color in its set that is different from the first vertex.

For the third test case, if the sets for all three vertices are $\{A, B\}$, it is impossible to satisfy the condition that "no two adjacent vertices are colored with the same color."

Subtasks

For 10% of the data, $1 \le n \le 3$. For 20% of the data, $1 \le n \le 6$. For 50% of the data, $1 \le n \le 1000$, $0 \le m \le 2000$. For 100% of the data, $1 \le n \le 10000$, $0 \le m \le 20000$, $1 \le T \le 10$.