CF1144F Graph Without Long Directed Paths

给定一个包含 $n$ 个顶点和 $m$ 条边的连通无向图。图中没有自环或重边。 你需要为该图的每条边定向，使得得到的有向图中不存在长度大于等于 $2$ 的路径（路径的长度指经过的边数）。

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$n - 1 \le m \le 2 \cdot 10^5$），分别表示顶点数和边数。 接下来的 $m$ 行，每行包含两个整数 $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)$，输入中不会出现 $(u_i, v_i)$ 和 $(v_i, u_i)$ 的重复。保证给定的图是连通的（任意两点之间都存在路径）。

如果无法为该图的边定向，使得得到的有向图中不存在长度大于等于 $2$ 的路径，则第一行输出 "NO"。 否则，第一行输出 "YES"，接下来输出一个长度为 $m$ 的二进制字符串。第 $i$ 个字符为 '0' 表示第 $i$ 条边应从 $u_i$ 指向 $v_i$，为 '1' 表示应从 $v_i$ 指向 $u_i$。边的编号顺序与输入顺序一致。

第一个样例对应的图如下： 其中一种可能的答案如下： 由 ChatGPT 4.1 翻译