By Ricardo Oliveira, UFPR Brazil
Analógimôn Go! is a very popular game. During his quest, the player travels across many cities capturing virtual little monsters called analógimôns.
There are many analógimôn species. Each species is associated with (exactly) one type, such as fire, water, electric, etc. Some species might be of the same type, while others might be of different types.
In the game’s official manual there is the information that some species are of the same type. However, the manual may not present this information for all pairs of species that are of the same type. For example, if the manual indicates that species a is of the same type of species b, and species b is of the same type of species c, then species a and c are certainly of the same type, even if this information is not present in the manual.
You have just captured an analógimôn of a certain species. Your task is to determine the smallest possible number of species that are certainly of the same type of the one you captured, according to the information present in the manual.
The input contains several test cases. The first line of each test case contains two integers N and M (1 ≤ N ≤ 1000, 0 ≤ M ≤ N(N-1)/2), the number of species and the number of information present in the manual, respectively. Species are numbered from 1 to N. The next M lines contains an information each. Each line contains two integers a and b (1 ≤ a, b ≤ N, a≠b), indicating that species a and b are of the same type. The last line contains an integer E (1 ≤ E ≤ N), indicating the species of the analógimôn you just captured.
The input ends with end-of-file (EOF).
For each test case, print a line containing an integer indicating the smallest possible number of species that are of the same type of your analógimon. Please notice that the species of your own analógimon must also be included.
|Input Sample||Output Sample|