問題文
高桥君 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