CF794D Labelling Cities

银行客户 Oleg 住在 Bankopolia。有 $n$ 个城市，有些城市两两之间通过双向道路直接相连。城市编号为 $1$ 到 $n$。Bankopolia 总共有 $m$ 条道路，第 $i$ 条道路连接了城市 $u_{i}$ 和 $v_{i}$。保证从任意一个城市出发都能通过若干条道路到达任何其他城市。 Oleg 想给每个城市标一个标签。假设城市 $i$ 的标签为 $x_{i}$。那么，要求对于所有城市对 $(u,v)$，当且仅当城市 $u$ 和 $v$ 之间有道路直接相连时，满足 $|x_{u}-x_{v}| \leq 1$。 Oleg 想知道，是否存在一种满足要求的标记方式。若存在，请给出一个满足要求的标记例子；若不存在，请说明不可能。

输入第一行包含两个用空格分隔的整数 $n$ 和 $m$（$2 \leq n \leq 3 \cdot 10^{5}$，$1 \leq m \leq 3 \cdot 10^{5}$），分别表示城市数和道路数。 接下来 $m$ 行，每行包含两个用空格分隔的整数 $u_{i}$ 和 $v_{i}$（$1 \leq u_{i}, v_{i} \leq n$，$u_{i} \neq v_{i}$），表示第 $i$ 条道路连接了城市 $u_{i}$ 和 $v_{i}$。保证每对城市之间至多只有一条道路，并且所有城市两两之间总是连通的。

如果不存在满足要求的标记方式，输出一行 "NO"（不包含引号）。 否则，第一行输出 "YES"（不包含引号）。第二行输出 $n$ 个用空格分隔的整数 $x_{1},x_{2},...,x_{n}$，满足 $1 \leq x_{i} \leq 10^{9}$，并且对于所有城市对 $(u, v)$，当且仅当城市 $u$ 和 $v$ 之间有道路直接相连时，有 $|x_{u}-x_{v}| \leq 1$。

对于第一个样例，$x_{1}=2$，$x_{2}=3$，$x_{3}=x_{4}=1$ 是一个可行的标记。确实，$(3,4)$，$(1,2)$，$(1,3)$，$(1,4)$ 是唯一的标签差不超过 $1$ 的城市对，这些正好是 Bankopolia 的道路。 对第二个样例，所有城市编号的标签差都不超过 $1$，且所有城市两两之间都有道路相连。 对最后一个样例，不可能构造出符合要求的标签安排。 由 ChatGPT 5 翻译