题目描述

一年前，Caroline 曾请你帮助解决一道仙人掌图问题。在过去的一年里，她深入研究了仙人掌图。今天，轮到她向你提出问题了。

给定一个 不含桥的仙人掌图，并且满足：

每一个奇数长度简单环的长度，都不小于该仙人掌图中奇数长度简单环的总数。

你需要判断，是否可以给仙人掌图的每条边标记一个正整数，使得以下条件同时成立：

• 设使用的最大标号为 $t$，则整数 $1,2,\ldots,t$ 均至少被使用一次。你不需要最小化或最大化 $t$；
• 对于图中的每个顶点 $v$，所有与 $v$ 相接的边的标号互不相同，并且这些标号恰好构成一段连续整数区间。

若删除一条边后，图的连通分量数增加，则称这条边为 桥。

仙人掌图 是一个连通无向图，其中每条边至多属于一个简单环。直观地说，它是允许出现若干环的树的推广。

本题中的仙人掌图不含重边，也不含自环。

输入格式

第一行包含两个整数 $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,\qquad u\ne v,$$

表示仙人掌图中的一条边。

保证输入的图满足题目描述中的全部限制。

输出格式

若不存在满足条件的标号方案，输出一行：

NO

否则输出三行：

• 第一行输出 YES；
• 第二行输出整数 $t$，表示不同标号的数量，其中 $1\le t\le m$；
• 第三行输出 $m$ 个整数 $c_1,c_2,\ldots,c_m$，其中 $c_i$ 表示输入中第 $i$ 条边的标号，并满足 $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

样例示意图

样例1示意图

样例2示意图