beecrowd | 2894


By Paulo E. D. Pinto, UERJ- Universidade do Estado do Rio de Janeiro BR Brazil

Timelimit: 1

We are in an African country, where a dangerous virus has just arrived in a big city. The country will have to take extreme measures so that it does not spread. The only way out will be to block roads that arrive in infected cities. But the country only has the money to block a single stretch of road. In this country there is always at least one way between two cities. The Sanitary Surveillance wants to find out if there is a stretch of road that, when blocked, separates the rest of the country from the infected area.

You will help by making a program to identify if there is such an excerpt and indicate the maximum number of cities that can be isolated from the virus. Note that there may be more than one road stretch between two cities.


The first input line is an integer  (1 ≤ ≤ 100), the number of test cases. The description of test cases is given next. The description of each test is made in several lines. The first line contains 3 integers: N (1 ≤ ≤ 1000), the number of cities of the country, (N-1≤ 10000), the number of roads and    (1 ≤ N), the number of the infected city. The next M lines contains 2 integers each, describing one road between two cities. The cities are numbered from 1 to N.


For each test case print the maximum number of cities that can be isolated by blocking a stretch of road. If there is not an excerpt with the characteristics searched for, answer 0.

Input Sample Output Sample

9 10 3
1 3
4 2
3 4
5 3
4 5
6 5
7 6
6 5
8 7
8 9
4 4 1
1 2
2 3
3 4
1 4