← 返回题目列表

Codeforces · 794/D

D. 标记城市

中文机器翻译题面 查看原题

银行客户 Oleg 住在 Bankopolia。 Bankopolia 有 n 个城市,其中一些城市通过双向道路直接相连。城市编号为 1 到 n。 Bankopolia共有m条道路,第i条道路连接城市ui和vi。保证从每个城市都可以使用某些道路前往任何其他城市。

Oleg想给每个城市贴上标签。假设城市i的标签等于xi。那么,对于所有城市对 (u, v) 必须满足条件 |xu - xv| ≤ 1 当且仅当有一条道路连接 u 和 v 时成立。

奥列格想知道这样的标签是否可能。如果该任务是可能的,请找到此类标签​​的示例,否则说明该任务是不可能的。

输入

输入的第一行包含两个空格分隔的整数 n 和 m (2 ≤ n ≤ 3·105, 1 ≤ m ≤ 3·105) - 城市数量和道路数量。

接下来是 m 行。第 i 行包含两个空格分隔的整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - 由第 i 条道路连接的城市。保证每对城市之间最多有一条道路,并且可以使用某些道路从任何城市前往任何其他城市。

输出

如果无法实现所需的标签,则输出包含字符串“NO”(不带引号)的单行。

否则,在第一行输出字符串“YES”(不带引号)。在下一行,输出 n 个空格分隔的整数,x1, x2, ..., xn。对于所有 i,条件 1 ≤ xi ≤ 109 必须成立,对于所有城市对 (u, v),条件 |xu - xv| 必须成立。当且仅当有一条道路连接 u 和 v 时,≤ 1 必须成立。

示例

输入 #1

4 4
1 2
1 3
1 4
3 4

输出 #1

YES
2 3 1 1

输入 #2

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

输出 #2

YES
1 1 1 1 1

输入 #3

4 3
1 2
1 3
1 4

输出 #3

NO

注意

对于第一个样本,x1 = 2、x2 = 3、x3 = x4 = 1 是有效标签。事实上,(3, 4)、(1, 2)、(1, 3)、(1, 4) 是唯一标签差异不大于 1 的城市对,而这些正是 Bankopolia 的道路。

对于第二个样本,所有城市对的标签差异不大于 1,并且所有城市对都有一条道路连接它们。

对于最后一个样本,不可能构建满足给定约束的标签。