← 返回题目列表

Codeforces · 241/E

E. 航班

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

LiLand是一个国家,由n个城市组成。城市编号为 1 到 n。这个国家众所周知是因为它有一个非常奇怪的交通系统。有许多单程航班可以在城市之间旅行,但航班的安排方式是,一旦离开一个城市,您将永远无法再返回该城市。

以前每个航班正好一小时,但最近Lily成为了新的交通系统经理,她想更改一些航班的持续时间。具体来说,她希望将某些航班的持续时间更改为恰好 2 小时,这样从城市 1 到城市 n 的所有行程无论路径如何,都花费相同的时间。

你的任务是帮助莉莉更改航班的持续时间。

输入

输入的第一行包含两个整数 n 和 m (2 ≤ n ≤ 1000; 1 ≤ m ≤ 5000),指定城市数量和航班数量。

接下来的 m 行中的每一行都包含两个整数 ai 和 bi (1 ≤ ai < bi ≤ n),指定从城市 ai 到城市 bi 的单向航班。保证存在一种使用给定航班从城市 1 到城市 n 的方式。保证不存在形成循环路径的航班序列,并且没有两个航班在同一对城市之间。

输出

如果 Lily 无法完成她的任务,请在输出的唯一行上打印“No”(不带引号)。

否则,在输出的第一行打印“Yes”(不带引号),然后在接下来的 m 行中的每一行打印一个整数 ansi (1 ≤ ansi ≤ 2),作为新交通系统中的航班持续时间。您应该按照输入中给出的航班顺序打印这些数字。

如果输入有多个解,则输出其中任意一个。

示例

输入 #1

3 3
1 2
2 3
1 3

输出 #1

Yes
1
1
2

输入 #2

4 4
1 2
2 3
3 4
1 4

输出 #2

No

输入 #3

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

输出 #3

Yes
1
1
1
2
1
2