Flights

## 题目描述 LiLand 是一个由 $n$ 个城市组成的国家。城市从 $1$ 到 $n$ 编号。LiLan奇特的交通系统闻名天下。它的城市由许多单向航线连接，但是航线特殊的安排的方案导致：一旦离开某个城市，你就不可能再回来了。 从前，每条航线的航程一小时。但最近 Lily 成为了该国交通系统的新经理。她想把一些航线的航程改为 $2$ 小时，使得所有从城市 $1$ 到城市 $n$ 的路线的总航程都相同。 你的任务是帮助 Lily 改变航线的航程。 ## 输入格式 输入第一行包含两个整数 $n$ 和 $m$ $(2 \le n \le 1000),(1 \le m \le 5000)$ ，分别表示城市数和航线数。 接下来 $m$ 行，每行两个整数 $a_{i},b_{i} (1 \le a_{i},b_{i} \le n)$，表示一条从城市 $a_{i}$ 到城市 $b_{i}$ 的单向航线。保证至少存在一条从城市 $1$ 到 $n$ 的路线。保证不存在环状的路线，保证不存在两条航线连接同一对城市。 ## 输出格式 如果 Lily 不可能达成目的，输出仅一行 `No`。 否则，第一行输出 `Yes`，接下来 $m$ 行，每行输出一个整数 $ans_{i}$ 表示第 $i$ 条航线的航程。请务必按航线输入的顺序输出。 如果多解，输出任一解。

LiLand is a country, consisting of $ n $ cities. The cities are numbered from 1 to $ n $ . The country is well known because it has a very strange transportation system. There are many one-way flights that make it possible to travel between the cities, but the flights are arranged in a way that once you leave a city you will never be able to return to that city again. Previously each flight took exactly one hour, but recently Lily has become the new manager of transportation system and she wants to change the duration of some flights. Specifically, she wants to change the duration of some flights to exactly 2 hours in such a way that all trips from city 1 to city $ n $ take the same time regardless of their path. Your task is to help Lily to change the duration of flights.

First line of the input contains two integer numbers $ n $ and $ m $ $ (2<=n<=1000; 1<=m<=5000) $ specifying the number of cities and the number of flights. Each of the next $ m $ lines contains two integers $ a_{i} $ and $ b_{i} $ $ (1<=a_{i}&lt;b_{i}<=n) $ specifying a one-directional flight from city $ a_{i} $ to city $ b_{i} $ . It is guaranteed that there exists a way to travel from city number 1 to city number $ n $ using the given flights. It is guaranteed that there is no sequence of flights that forms a cyclical path and no two flights are between the same pair of cities.

If it is impossible for Lily to do her task, print "No" (without quotes) on the only line of the output. Otherwise print "Yes" (without quotes) on the first line of output, then print an integer $ ans_{i} $ $ (1<=ans_{i}<=2) $ to each of the next $ m $ lines being the duration of flights in new transportation system. You should print these numbers in the order that flights are given in the input. If there are multiple solutions for the input, output any of them.

3 3
1 2
2 3
1 3

Yes
1
1
2

4 4
1 2
2 3
3 4
1 4

No

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

Yes
1
1
1
2
1
2