F - 順位表 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は N 人の参加者が参加するプログラミングコンテストに参加しました。各参加者には 1 から N までの番号が振られており、高橋君は参加者 1 でした。

このコンテストでは順位表を見ることが出来なかったため、高橋君は自分の順位が分かりません。高橋君はコンテスト後の懇親会で「参加者 A_i は参加者 B_i よりも順位が高い」という情報を M 個入手しました。高橋君はこの情報をもとに、自分の順位として考えられるもののうち最も高いものを計算してみることにしました。ただし、最も高い順位は 1 位で、最も低い順位は N 位です。また、同順位に 2 人以上の参加者がいることはありません。

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
A_2 B_2
:
A_M B_M
  • 1 行目には、コンテストの参加者の人数を表す整数 N (2 ≦ N ≦ 50) と 高橋君が得た情報の個数を表す整数 M (1 ≦ M ≦ 50) が空白区切りで与えられる。
  • 2 行目からの M 行では、高橋君が得た情報が与えられる。このうち i 行目には、i 番目の情報を表す 2 つの整数 A_i, B_i (1 ≦ A_i ≦ N, 1 ≦ B_i ≦ N, A_i \neq B_i) が空白区切りで与えられる。これは、参加者 A_i が参加者 B_i よりも順位が高かったという情報を表す。
  • 矛盾するような情報が与えられないこと、同じ情報が 2 回以上与えられないことが保証される。

出力

高橋君、すなわち参加者 1 の順位として考えられるもののうち最も高い順位を表す 1 つの整数を 1 行に出力せよ。

入力例1

5 3
2 1
3 2
1 5

出力例1

3

3 つの情報はそれぞれ、

  • 参加者 2 は参加者 1 よりも順位が高い。
  • 参加者 3 は参加者 2 よりも順位が高い。
  • 参加者 1 は参加者 5 よりも順位が高い。

です。順位表としては以下のようなものが考えられます。

  • 1 位：参加者 3
  • 2 位：参加者 2
  • 3 位：参加者 1
  • 4 位：参加者 4
  • 5 位：参加者 5

この場合、参加者 1 である高橋君は 3 位です。 また、高橋君が 2 位以上である順位表は存在しないため、3 を出力します。

入力例2

3 2
2 1
2 3

出力例2

2

入力例3

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

出力例3

5