8.6 Thieves of Codeland

Score: 60pts

Time Limit: 1.00 sec

The kingdom of Codeland consists of several villages. For ease of administration, the king of Codeland has assigned a number to each village. The villages are numbered from 1 to \(n\) where \(n\) is the total number of villages in Codeland. The villages are connected to each other by means of highways. These highways are bidirectional. There are a total of \(m\) highways. The odd thing about these highways is that each highway is of the exact same length. The king of Codeland lives in the capital village, which is numbered \(a\).

One day the king of Codeland manages to get hold of a group of thieves. He wants to punish them and so he plans to send them on a journey to the village which is farthest from the capital of Codeland (or simply the village to which it will take the maximum number of highways to reach from the capital). He does not know which village is the farthest from the capital and so he asks you, his advisor, to tell him which is the farthest village from the capital.

You are given inputs \(n\), \(m\) and \(a\) and a list of villages between which there is a highway. You have to output the village number of the village which is farthest from the capital. There may exist some villages to which there is no highway and you can ignore such villages.

One day the king of Codeland manages to get hold of a group of thieves. He wants to punish them and so he plans to send them on a journey to the village which is farthest from the capital of Codeland (or simply the village to which it will take the maximum number of highways to reach from the capital). He does not know which village is the farthest from the capital and so he asks you, his advisor, to tell him which is the farthest village from the capital.

You are given inputs \(n\), \(m\) and \(a\) and a list of villages between which there is a highway. You have to output the village number of the village which is farthest from the capital. There may exist some villages to which there is no highway and you can ignore such villages.

Constraints

\(2 \leq n \leq 1000\)

\(1 \leq m \leq 2000\)

\(1 \leq a \leq 1000\)

\(1 \leq u \leq 1000\)

\(1 \leq v \leq 1000\)

\(1 \leq m \leq 2000\)

\(1 \leq a \leq 1000\)

\(1 \leq u \leq 1000\)

\(1 \leq v \leq 1000\)

Input Format

The first line of the input contains three integers \(n\) - the number of villages in Codeland, \(m\) - the number of highways in Codeland and \(a\) - The village number of the capital of Codeland.

The next m lines of the input contain two integers \(u\) and \(v\). The integers are the village numbers of villages between which there exists a highway (highways are bidirectional)

The next m lines of the input contain two integers \(u\) and \(v\). The integers are the village numbers of villages between which there exists a highway (highways are bidirectional)

Output Format

For each test case, you have to output on a new line, the village number of the village which is farthest from the capital.

Example 1

Input:

5 4 1

1 2

1 3

1 4

4 5

Output:

5

Explanation:

The village number of the capital is 1. There exists 1 highway between villages 1and 2; 1 and 3; 1 and 4. Village 5 is not connected to the capital by a highway. One highway exists between village 4 and village 5. So village 5 is farthest from the capital (it takes 2 highways to reach village 5). So, the answer is 5.

5 4 1

1 2

1 3

1 4

4 5

Output:

5

Explanation:

The village number of the capital is 1. There exists 1 highway between villages 1and 2; 1 and 3; 1 and 4. Village 5 is not connected to the capital by a highway. One highway exists between village 4 and village 5. So village 5 is farthest from the capital (it takes 2 highways to reach village 5). So, the answer is 5.