CF2260F Edge Three-Coloring

给定一个包含 $n$ 个顶点和 $m$ 条边的无向连通图，其中 $m\le n+9$。 要求对图中的每条边涂上三种颜色之一（编号为 $1$ 到 $3$）。如果存在一条仅由颜色 $c$ 的边组成的从 $u$ 到 $v$ 的路径，则称顶点 $u$ 和 $v$ 在颜色 $c$ 下是可达的。 请判断是否存在一种对边的染色方案，满足以下条件： - 每种颜色至少有一条边被染上该颜色； - 对于每对颜色 $i$ 和 $j$，以及任意一对顶点 $u$ 和 $v$，如果 $u$ 和 $v$ 在颜色 $i$ 下可达且 $i

第一行包含一个整数 $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$； - 每个测试用例中的图无自环、无重边； - 每个测试用例中的图是连通的。

对于每个测试用例，若存在这样的染色方案，输出 YES，否则输出 NO。输出的字母大小写不限。

在第一个样例中，可以将第 $5$ 条边染成颜色 $1$，第 $1$ 条和第 $4$ 条边染成颜色 $2$，其余的边全部染成颜色 $3$。 由 ChatGPT 5 翻译