P5295 [Beijing NOI Qualifier Training 2019] A Hard Problem on Graphs

The title is fake.

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.

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 $T$ lines. For each test case, output `Yes` if a solution exists, otherwise output `No`.

### 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