CF1144F.Graph Without Long Directed Paths

You are given a connected undirected graph consisting of $n$ vertices and $m$ edges. There are no self-loops or multiple edges in the given graph.

You have to direct its edges in such a way that the obtained directed graph does not contain any paths of length two or greater (where the length of path is denoted as the number of traversed edges).

给你一个由 $n$ 个顶点和 $m$ 条边组成的连通无向图。给定图中不存在自环或重边。

你需要将它的边定向，使得所得的有向图不包含长度为二或更大的路径（路径长度定义为所经过的边的数量）。

The first line contains two integer numbers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le 2 \cdot 10^5$) — the number of vertices and edges, respectively.

The following $m$ lines contain edges: edge $i$ is given as a pair of vertices $u_i$, $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$). There are no multiple edges in the given graph, i. e. for each pair ($u_i, v_i$) there are no other pairs ($u_i, v_i$) and ($v_i, u_i$) in the list of edges. It is also guaranteed that the given graph is connected (there is a path between any pair of vertex in the given graph).

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$n - 1 \le m \le 2 \cdot 10^5$），分别表示顶点数和边数。

接下来的 $m$ 行描述各条边：第 $i$ 条边由一对顶点 $u_i$、$v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$）给出。给定图中不存在重边，即对任意一对 $(u_i, v_i)$，列表中不包含其他形如 $(u_i, v_i)$ 或 $(v_i, u_i)$ 的边。此外，保证给定图是连通的（图中任意两个顶点之间均存在路径）。

If it is impossible to direct edges of the given graph in such a way that the obtained directed graph does not contain paths of length at least two, print "NO" in the first line.

Otherwise print "YES" in the first line, and then print any suitable orientation of edges: a binary string (the string consisting only of '0' and '1') of length $m$. The $i$-th element of this string should be '0' if the $i$-th edge of the graph should be directed from $u_i$ to $v_i$, and '1' otherwise. Edges are numbered in the order they are given in the input.

如果无法将给定图的边定向，使得所得有向图不包含长度至少为 2 的路径，则在第一行输出 "NO"。

否则，在第一行输出 "YES"，然后输出任意一种满足条件的边定向方案：一个长度为 $m$ 的二进制字符串（仅由字符 '0' 和 '1' 组成）。该字符串的第 $i$ 个字符应为 '0'，表示图中第 $i$ 条边应从 $u_i$ 指向 $v_i$；否则（即从 $v_i$ 指向 $u_i$）应为 '1'。边的编号顺序与其在输入中出现的顺序一致。

The picture corresponding to the first example:

And one of possible answers:

第一个示例对应的图片：

其中一个可能的答案：