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

给你一个包含 $n$ 个顶点和 $m$ 条边的无向连通图，其中 $m \le n + 9$。

图中的每条边必须被染成三种颜色之一（颜色编号为 $1$ 至 $3$）。我们称顶点 $u$ 和 $v$ 在颜色 $c$ 下可达，当且仅当存在一条仅由颜色 $c$ 的边构成的从 $u$ 到 $v$ 的路径。

请判断是否存在一种边染色方案，使得以下条件均满足：

• 每种颜色至少有一条边被染成该颜色；
• 对任意两种颜色 $i$ 和 $j$（其中 $i < j$）以及任意两个顶点 $u$ 和 $v$，若 $u$ 和 $v$ 在颜色 $i$ 下可达，则它们在颜色 $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.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例以一行开始，该行包含两个整数 $n$ 和 $m$（$2 \le n \le 3000$；$n - 1 \le m \le n + 9$）—— 图中顶点和边的数量。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$）—— 第 $i$ 条边的两个端点。

输入的额外约束条件：

• 所有测试用例的 $n$ 之和不超过 $3000$；
• 每个测试用例中，图不含自环或重边；
• 每个测试用例中，图是连通的。

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.

对于每个测试用例，按如下方式输出答案：如果存在满足条件的边染色方案，则输出 YES；否则输出 NO。每个字母可使用任意大小写形式。

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

在第一个例子中，可以将第 $5$ 条边涂成颜色 $1$，第 $1$ 条和第 $4$ 条边涂成颜色 $2$，其余所有边涂成颜色 $3$。