Caroline 一年前曾向你寻求解决一个仙人掌图问题的帮助。在过去的一年中，她对仙人掌图进行了深入研究。今天，由她来提出这个问题。

给定一个无桥仙人掌图，且图中每个奇简单环的长度都大于或等于该仙人掌图中奇简单环的总数。你的任务是判断是否可以给仙人掌图的边分配正整数标签，使得满足以下条件：

• 设最大标签为 $t$。所有整数 $1, 2, \dots, t$ 均被用于标签中（注意，你不需要最小化或最大化 $t$ 的值）；
• 对于给定仙人掌图中的每个顶点 $v$，与顶点 $v$ 相连的边的标签必须互不相同，且构成一个连续的整数区间。

如果删除某条边会增加图中连通分量的数量，则称该边为桥。仙人掌图是一种连通无向图，其中每条边最多属于一个简单环。直观地说，仙人掌图是树的一种推广，允许存在一些环。仙人掌图中不允许存在多重边（一对顶点之间有多条边）和自环（连接顶点自身的边）。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($3 \le n \le 10^5$, $n \le m \le \lfloor \frac{3(n-1)}{2} \rfloor$)，分别表示仙人掌图的顶点数和边数。接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n; u \neq v$)，表示仙人掌图的一条边。给定的仙人掌图满足题目描述中的所有约束条件。

输出格式

如果无法找到满足题目条件的标签方案，输出一行单词 “NO”。否则，在第一行输出单词 “YES”。在第二行输出一个整数 $t$ ($1 \le t \le m$)，表示不同标签的数量。在第三行输出 $m$ 个整数 $c_i$ ($1 \le i \le m, 1 \le c_i \le t$)，表示各边的标签。

样例

输入 1

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

输出 1

NO

输入 2

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

输出 2

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