Background

The title is fake.

Problem Description

Xiao D encountered a problem in a graph theory exercise book:

The book shows an undirected graph and asks you to color each edge either black or white, such that the subgraph formed by all white edges has no cycles, and the subgraph formed by all black edges also has no cycles.

No matter how she tries, Xiao D feels that the problem in the book has no solution. She wants you to help confirm this.

Since this problem has many subtasks, each time Xiao D will give you the number of vertices $n$, the number of edges $m$, and the full edge set. You only need to tell Xiao D whether a solution exists.

Input Format

The first line contains a positive integer $T$, denoting the number of test cases.

For each test case, the first line contains two positive integers $n,m$, with the meaning as described in the statement.

Then follow $m$ lines. Each line contains two positive integers $u,v$, denoting an undirected edge from $u$ to $v$.

Output Format

Output $T$ lines. For each test case, output Yes if a solution exists, otherwise output No.

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

Yes
No
Yes

Hint

Constraints

For $20\%$ of the testdata: $1\le m \le 10$.

For $40\%$ of the testdata: $1\le n \le 15$.

For $70\%$ of the testdata: $1\le n \le 50$.

For $100\%$ of the testdata: $1\le n \le 501$, $1\le m \le 2n$, $1\le T \le 10$.

Translated by ChatGPT 5