CF2260F Edge Three-Coloring

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 $ .

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.

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.

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 $ .