\(7^{th}\) round (Croatian Olympiad in Informatics), April \(28^{th}\), 2012

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.

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.

\(7^{th}\) round (Croatian Olympiad in Informatics), April \(28^{th}\), 2012

The first line of input contains the two integers N and M (\(2 \le N \le 100\), \(2 \le M \le 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 \le A\), \(B \le 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.

생성자가 기록되지 않았습니다.

출처 COCI 2011/2012 Olympiad