Problem : 199 - KAMPANJA

Problem Statistics

Solved Member: 10　　Submission: 28　　User Tried: 10

Statement:

大選接近了，因此 Amabo Kcarab 總統準備要去 WDC 和 LA 兩地演講。為了要給總統足夠的保安資源，特工必須持續的監控所有總統會經過的城市。

當然，聯邦預算必須被合理的使用，因次總統並不會搭乘 AirForce-1(空軍一號)，而會搭乘一般的車子。而總統車隊的路線是由這群特工規劃的，從 WDC 出發經過 LA，再從 LA 回到 WDC，這樣才能確保特工必須監控的城市數量最少。

對於這個問題，總共有 N 個城市，這些城市的編號從 1~N，另外有 M 條單向道路。WDC 的編號為 1，而 LA 為 2。

請你寫一支程式計算最少需要被監控的城市數量，你所規劃的道路必須經過 WDC 和 LA，再回到 WDC。

Input:Output:

第一行包含兩個整數 N 和 M(2 ≤ N ≤ 100, 2 ≤ M ≤ 200)，代表城市數量和單向道路數量。

接下來的 M 行，每行有兩個整數A, B(1 ≤ A, B ≤ N)，不會有重複的路徑，但可能會存在兩個城市由相反方向互相連通。〈注意本題為單向道路〉

註：測資保證一定存在至少一組路徑滿足題敘。

請輸出唯一一行，包含一個整數，代表最少需要監控的城市數量。

Sample Input:Sample Output:

SAMPLE A:
6 7
1 3
3 4
4 5
5 1
4 2
2 6
6 3

SAMPLE B:
9 11
1 3
3 4
4 2
2 5
5 3
3 6
6 1
2 7
7 8
8 9
9 1

SAMPLE A:
6

SAMPLE B:
6

HINT:

佔本題 20% 的測資，N 最大為 20。

對於第一筆範例測資，總統可以經過這樣的路徑：1 -> 3 -> 4 -> 2 -> 6 -> 3 -> 4 -> 5 -> 1。因此，他需要經過的城市數量最少為6。

Source:

COI 2012

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	3000ms	131072kb
0-2	3000ms	131072kb
1	3000ms	131072kb	10
2	3000ms	131072kb	10
3	3000ms	131072kb	10
4	3000ms	131072kb	10
5	3000ms	131072kb	10
6	3000ms	131072kb	10
7	3000ms	131072kb	10
8	3000ms	131072kb	10
9	3000ms	131072kb	10
10	3000ms	131072kb	10