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
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.
Input Specification
The first line of input contains the two integers
Each of the following
Output Specification
The first and only line of output must contain the minimum number of cities that need to be monitored.
Scoring
In test data worth a total of
Note: Test data will ensure that a solution will always exist.
Sample Input 1
6 7
1 3
3 4
4 5
5 1
4 2
2 6
6 3
Sample Output 1
6
Explanation for Sample Output 1
The President can take the following route:
Sample Input 2
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 Output 2
6
Comments