← 返回题目列表

Codeforces · 1144/F

F. 没有长有向路径的图

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

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

您必须以这样的方式引导其边,使得获得的有向图不包含任何长度为 2 或更大的路径(其中路径的长度表示为遍历的边的数量)。

输入

第一行包含两个整数 $$$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$$$) 给出。给定图中没有多重边,i。 e.对于每对 ($$$u_i, v_i$$$),边列表中没有其他对 ($$$u_i, v_i$$$) 和 ($$$v_i, u_i$$$)。还保证给定图是连通的(给定图中任意一对顶点之间都存在路径)。

输出

如果不可能以这样的方式引导给定图的边,使得获得的有向图不包含长度至少为二的路径,则在第一行打印“NO”。

否则在第一行打印“YES”,然后打印任何合适的边缘方向:长度为$$$m$$$的二进制字符串(仅由“0”和“1”组成的字符串)。如果图形的第 $$$i$$$ 边应从 $$$u_i$$$ 指向 $$$v_i$$$,则该字符串的第 $$$i$$$ 个元素应为“0”,否则为“1”。边按照输入中给出的顺序进行编号。

示例

输入 #1

6 5
1 5
2 1
1 4
3 1
6 1

输出 #1

YES
10100

注意

第一个例子对应的图片:

可能的答案之一: