暂无测试数据。

Description

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

Input

输入格式

第一行：两个整数n和m

接下来m行每行两个整数，其中第i行表示si和ti

Output

输出格式

输出一个数表示答案。

Sample 1

Input

6 7
1 3
3 4
4 5
5 1
4 2
2 6
6 3

Output

6

Sample 2

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

Hint

数据范围
对于20% 的数据，满足n≤20。
对于100% 的数据，满足2≤n≤100，2≤m≤200

Source

COCI, 2011/2012, 决赛, KAMPANJA