A1465.[COCI-2011_2012-olympiad]#1 KAMPANJA

The elections are nearing, so President Amabo Kcarab is planning a tour of the States, with speeches in WDC and LA. To provide adequate security, the Secret Service needs to constantly monitor all cities that the President will pass through (including WDC and LA).
Of course, the federal budget needs to be spent responsibly, so the President will not be using AF1, but will be travelling by car. Also, the Secret Service will plan the President's tour from WDC to LA and back to WDC such that the least possible number of cities needs to be monitored.
For this problem, assume that the States consist of N cities, denoted by numbers from 1 to N, and M unidirectional Interstates, with each Interstate linking two different cities. WDC is city number 1, LA number
2.
Write a program to compute the minimum number of cities that need to be monitored such that there exists a path from WDC to LA and back to WDC passing only through monitored cities.

The first line of input contains the two integers N and M (2 ≤ N ≤ 100, 2 ≤ M ≤ 200), the number of cities and the number of Interstates linking the cities, respectively.
Each of the following M lines contains two different integers A, B (1 ≤ A, B ≤ N), the beginning and ending city served by the given Interstate. No two Interstates link the same two cities in the same direction, but two Interstates can link the same two cities in opposite directions.

The first and only line of output must contain the minimum number of cities that need to be monitored.

In test data worth a total of 20 points, N will be at most 20.
Note: Test data will ensure that a solution will always exist.

First sample description: The President can take the following route: 1 -> 3 -> 4 -> 2 -> 6 -> 3 -> 4
-> 5 -> 1. Since he needs to pass through each city at least once, the solution is 6.