无桥仙人掌图

时间限制：3 秒 内存限制：1024 兆字节

一年前，Caroline 曾请你帮忙解决一个仙人掌图问题。在过去的一年里，她对仙人掌图进行了深入的研究。今天，轮到她来出题了。

题目描述

给你一张无桥仙人掌图，并且图中每一个奇简单环的长度都大于等于图中奇简单环的总数。

你的任务是判断是否可以给图中的边分配正整数标签，使得以下条件成立：

1. 设最大的标签值为 $t$。标签必须恰好使用了 $1, 2, \dots, t$ 中的每一个整数（你不需要最小化或最大化 $t$ 的值）；
2. 对于图中的每一个顶点 $v$，与 $v$ 相连的所有边的标签必须互不相同，且恰好构成一段连续整数。

相关定义

• 桥：如果删除一条边会导致图的连通分量数量增加，则这条边称为桥。题目给定的图不含桥。
• 仙人掌图 (Cactus)：一种连通无向图，满足每条边至多在一个简单环上。直观来说，仙人掌图是允许存在环的树的推广。仙人掌图中不存在重边和自环。

输入格式

第一行包含两个整数 $n$ 和 $m$ （$3 \le n \le 10^5,\ n \le m \le \left\lfloor \frac{3(n-1)}{2} \right\rfloor$） 分别表示图的顶点数和边数。

接下来 $m$ 行，每行两个整数 $u, v$ （$1 \le u, v \le n,\ u \neq v$） 表示图中的边。

输入保证给定的图满足题目描述中的所有约束条件。

输出格式

如果无法构造出满足条件的标签，输出一行 NO。

否则：

1. 第一行输出 YES；
2. 第二行输出一个整数 $t$（$1 \le t \le m$），表示标签的最大值；
3. 第三行输出 $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

输出

NO

样例 2

输入

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

输出

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