P4429 [BJOI2018] Coloring

pupil likes coloring the vertices of a graph. One day, master wanted to make things difficult and gave him a simple undirected graph (no multiple edges or self-loops). For each vertex, master assigned a color set of size $2$, and pupil can only choose one color from that set for the vertex. master wants pupil’s coloring to be such that no two vertices connected by an edge are colored with the same color. Now pupil wants to know whether, no matter what color sets master assigns, he can always color the graph as required.

The input contains multiple test cases. The first line contains a positive integer $T$, the number of test cases. For each test case, the first line contains two space-separated integers $n, m$, the number of vertices and edges in the undirected graph. Then follow $m$ lines, each containing two space-separated positive integers $i, j$, indicating an edge between vertices $i$ and $j$. Vertices are numbered from $1$.

For each test case, if pupil can always color the graph regardless of the assigned color sets, output a line with the string `YES`; otherwise, output a line with the string `NO`.

Sample explanation. For the first test case, if the sets for the first and second vertices are $\{A, B\}$, for the third and fourth vertices are $\{A, C\}$, and for the fifth and sixth vertices are $\{B, C\}$, then the odd-indexed vertices must use at least two colors, and the even-indexed vertices must use at least two colors. Therefore, at least one odd-indexed vertex and one even-indexed vertex share the same color. But there is an edge between every pair of odd-indexed vertices and between every pair of even-indexed vertices, so the requirement “no two adjacent vertices share the same color” cannot be satisfied. For the second test case, regardless of the two sets, color the first vertex with any color from its set, and color the second vertex with a color from its set that is different from the first vertex’s color. For the third test case, if all three vertices have the set $\{A, B\}$, then the requirement “no two adjacent vertices share the same color” cannot be satisfied. Constraints: - For $10\%$ of the testdata, $1 \leq n \leq 3$. - For $20\%$ of the testdata, $1 \leq n \leq 6$. - For $50\%$ of the testdata, $1 \leq n \leq 1000$, $0 \leq m \leq 2000$. - For $100\%$ of the testdata, $1 \leq n \leq 10000$, $0 \leq m \leq 20000$, $1 \leq T \leq 10$. - There are also $5$ unscored hack testdata. Translated by ChatGPT 5