← 返回题目列表

AtCoder · code_thanks_festival_14_quala_f

F. 积分榜

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

問題文

高桥君 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