Problem Description

Takahashi participated in a programming contest with $ N $ participants. Each participant is assigned a number from $ 1 $ to $ N $, and Takahashi is participant $ 1 $.

Since the ranking table was not available during the contest, Takahashi does not know his rank. Takahashi obtained $ M $ pieces of information at the post-contest social gathering, which stated "Participant $ A_i $ ranked higher than participant $ B_i $." Takahashi decided to use this information to calculate the highest possible rank he could have. The highest rank is $ 1 $ and the lowest rank is $ N $. Also, there are no ties; each rank is unique.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : $ A_M $ $ B_M $

• The first line contains two integers: $N\ (2\ ≦\ N\ ≦\ 50)$, representing the number of participants, and $M\ (1\ ≦\ M\ ≦\ 50)$, representing the number of pieces of information Takahashi obtained, separated by a space.
• The next $ M $ lines contain the information Takahashi obtained. The $ i $-th line contains two integers $A_i,\ B_i\ (1\ ≦\ A_i\ ≦\ N,\ 1\ ≦\ B_i\ ≦\ N,\ A_i\ \neq\ B_i)$ separated by a space, indicating that participant $ A_i $ ranked higher than participant $ B_i $.
• It is guaranteed that no contradictory information is given and that the same information is not given more than once.

Output Format

Output a single integer on one line, representing the highest possible rank for Takahashi, i.e., participant $ 1 $.

Sample Input and Output

Sample Input #1

5 3
2 1
3 2
1 5

Sample Output #1

3

Sample Input #2

3 2
2 1
2 3

Sample Output #2

2

Sample Input #3

8 10
3 8
2 1
4 6
3 6
4 1
5 8
2 4
7 6
7 2
3 1

Sample Output #3

5

Notes/Hints

Sample Explanation 1

The three pieces of information are:
- Participant $ 2 $ ranked higher than participant $ 1 $.
- Participant $ 3 $ ranked higher than participant $ 2 $.
- Participant $ 1 $ ranked higher than participant $ 5 $.

A possible ranking table is as follows:
- $ 1 $st place: Participant $ 3 $
- $ 2 $nd place: Participant $ 2 $
- $ 3 $rd place: Participant $ 1 $
- $ 4 $th place: Participant $ 4 $
- $ 5 $th place: Participant $ 5 $

In this case, Takahashi, who is participant $ 1 $, is ranked $ 3 $. Since there is no ranking table where Takahashi is ranked $ 2 $ or higher, output $ 3 $.

见题面 Input 部分

见题面 Output 部分