3479. 现任总统的巡游

单点时限: 2.0 sec

内存限制: 256 MB

某国有 $n$ 个城市,以 $1$ 到 $n$ 的整数编号,$1$ 号城市是首都。这些城市之间有 $m$ 条道路,每条道路都是单向通行的,第 $i$ 条道路的起点 $s_i$ 号城市,终点是 $t_i$ 号城市。这个国家的大选在即,现任总统打算从首都出发,沿路发表演讲,一直巡游到最支持他的城市 $2$ 号城市,然后再从 $2$ 号城市返回首都。凡是总统待过的城市,必须配置保安。请你找出一条线路,使得需要配置保安的城市数量尽量少,输入数据保证线路总是存在的。

输入格式

第一行:两个整数 $n$ 和 $m$。$(2\le n\le 100, 2\le m\le 200)$

接下来 $m$ 行每行两个整数,其中第 $i$ 行表示 $s_i$ 和 $t_i$。

输出格式

输出一个整数。

样例

Input
6 7
1 3
3 4
4 5
5 1
4 2
2 6
6 3
Output
6
Input
9 11
1 3
3 4
4 2
2 5
5 3
3 6
6 1
2 7
7 8
8 9
9 1
Output
6

提示

对于第一组样例:最优解为 1→3→4→2 , 2→6→3→4→5→1

11 人解决,19 人已尝试。

16 份提交通过,共有 73 份提交。

6.5 EMB 奖励。

创建: 2 年,9 月前.

修改: 2 年,8 月前.

最后提交: 1 年,7 月前.

来源: N/A

题目标签
DP