边三染色

题目描述

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

每条边必须用三种颜色之一染色，颜色编号为 $1$ 到 $3$。如果存在一条从 $u$ 到 $v$ 且仅由颜色为 $c$ 的边组成的路径，则称顶点 $u$ 和 $v$ 在颜色 $c$ 下可达。

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

• 对于每种颜色，至少有一条边被染成该颜色；
• 对于每一对颜色 $i$ 和 $j$，以及每一对顶点 $u$ 和 $v$，以下条件成立：如果 $u$ 和 $v$ 在颜色 $i$ 下可达，且 $i < j$，那么它们在颜色 $j$ 下也可达。

输入格式

第一行包含一个整数 $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$ 条边的两个端点。

输出格式

对于每个测试用例，如果存在这样的边染色方案，输出 YES；否则输出 NO。每个字母可以使用任意大小写。

样例输入

4
4 6
1 2
2 3
3 1
1 4
2 4
3 4
3 3
1 2
2 3
3 1
7 9
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 1
5 8
1 2
2 3
3 4
4 1
5 1
5 2
5 3
5 4

样例输出

YES
NO
NO
YES

样例解释

对于样例输入中的第一个测试用例，有 $n=4$ 个顶点和 $m=6$ 条边，边的输入顺序依次为 $(1,2)$、$(2,3)$、$(3,1)$、$(1,4)$、$(2,4)$、$(3,4)$，这是一个 $4$ 个顶点的完全图。

按照以下方式染色：

• 第 $5$ 条边 $(2,4)$ 染颜色 $1$；
• 第 $1$ 条边 $(1,2)$ 和第 $4$ 条边 $(1,4)$ 染颜色 $2$；
• 第 $2$、$3$、$6$ 条边染颜色 $3$。

颜色 $1$ 中只有边 $(2,4)$，因此在颜色 $1$ 下可达的顶点对只有 $(2,4)$。颜色 $2$ 包含边 $(1,2)$ 和 $(1,4)$，所以 $2$ 和 $4$ 通过顶点 $1$ 连通，可达。颜色 $3$ 包含边 $(2,3)$、$(3,1)$ 和 $(3,4)$，因此 $2$ 和 $4$ 可以通过 $2 \to 3 \to 4$ 连通，$1$ 和 $2$ 可以通过 $1 \to 3 \to 2$ 连通，$1$ 和 $4$ 可以通过 $1 \to 3 \to 4$ 连通。

因此颜色 $1$ 下可达的顶点对在颜色 $2$ 下也可达，颜色 $2$ 下可达的顶点对在颜色 $3$ 下也可达，并且每种颜色都至少使用了一次。该方案满足全部条件，所以第一个测试用例输出 YES。

数据范围

• $1 \le t \le 1000$
• $2 \le n \le 3000$
• $n - 1 \le m \le n + 9$
• $1 \le u_i, v_i \le n$ 且 $u_i \ne v_i$
• 所有测试用例中 $n$ 的总和不超过 $3000$
• 每个测试用例中图无自环和重边
• 每个测试用例中图是连通的