TopCoder

User's AC Ratio

94.9% (93/98)

Submission's AC Ratio

42.8% (131/306)

Tags

Description

義大利黑手黨內有許多家族,家族定義如下:

有n個黨員,依名次為1~n

假如a和b有關係,則說a和b是同一家族的

此時其他與a、b有關係的人都會被視為此家族的人

而每一個家族的人都會選擇當中名次最高者當首領

現在給你其中一個彭哥列家族成員k

要你找出其首領

Input Format

本題有多組測資

每組測資第一行有兩數,n、m(有幾組關係) (m≤n≤10000)

接下來m行,每行兩數,a和b,代表有關聯的兩人之編號

最後,輸入k,為已知的彭哥列家族成員編號

Output Format

對每組測資輸出一數,即為首領編號

Sample Input

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

Sample Output

1

Hints

Problem Source

原TIOJ1312 / TFcis10 留社考。Problem Setter:zenixls2

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 262144