给你一个无向图。你必须为图中的每个顶点染色，使得满足以下两个条件：

• 图中不存在单色环（即不存在所有顶点颜色都相同的环）。
• 对于图中出现的每对不同的颜色 $c_1, c_2$，都存在一个仅包含颜色 $c_1$ 和 $c_2$ 的双色环（即该环包含至少一个颜色为 $c_1$ 的顶点，至少一个颜色为 $c_2$ 的顶点，且不包含任何其他颜色的顶点）。

报告是否可以进行这样的染色，如果可以，提供一种有效的染色方案。

（图中的环是指一个由不同顶点组成的序列 $(v_1, \dots, v_c)$，其中 $c \ge 3$，满足对于所有 $1 \le i < c$，顶点 $v_i$ 和 $v_{i+1}$ 之间都有一条边，且 $v_c$ 和 $v_1$ 之间也有一条边。）

输入格式

第一行包含一个整数 $T$（$1 \le T \le 2000$），表示需要处理的独立测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^6$，$1 \le m \le 3 \cdot 10^6$），分别表示图中的顶点数和边数。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示第 $i$ 条边连接的两个顶点。每对顶点之间最多只有一条边。

所有测试用例的 $(n + m)$ 之和不超过 $4 \cdot 10^6$。

输出格式

对于每个测试用例，如果不存在有效的染色方案，输出单行 “NO”。否则，输出一行 “YES”，后跟一个整数 $C$（$1 \le C \le n$），表示你使用的颜色数量。

接着，输出一行包含 $n$ 个介于 $1$ 和 $C$ 之间的整数，其中第 $i$ 个整数表示分配给顶点 $i$ 的颜色。对于所有 $1 \le i \le C$，不应存在顶点颜色均为 $i$ 的环；且对于所有 $1 \le i < j \le C$，必须存在一个顶点颜色仅为 $i$ 和 $j$ 的环。如果存在多种可能的染色方案，你可以输出其中任意一种。

我们强烈建议在此题中使用快速输入输出（Fast I/O）。

样例

输入样例 1

2
5 8
1 2
1 3
1 4
2 3
5 1
4 3
4 5
5 2
4 2
1 2
3 4

输出样例 1

YES 3
1 2 2 3 3
YES 1
1 1 1 1

说明

下图展示了第一个样例的一种可能染色方案。不存在顶点颜色相同的环，且对于每对颜色，都存在一个仅包含这两种颜色的环：对于颜色 1 和 2，环为 $(1, 2, 3)$；对于颜色 1 和 3，环为 $(1, 4, 5)$；对于颜色 2 和 3，环为 $(2, 3, 4, 5)$。