TopCoder

Caido
Waimai

User's AC Ratio

93.6% (280/299)

Submission's AC Ratio

42.1% (461/1096)

Tags

Description

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

n 個黨員,依名次為 1n

假如 ab 有關係,則說 ab 是同一家族的

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

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

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

要你找出其首領

Input Format

本題有多組測資

每組測資第一行有兩數 n,m

其中 m 代表有幾組關係,mn10000

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

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

Output Format

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

Sample Input 1

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

Sample Output 1

1

Hints

Problem Source

原TIOJ1312 / TFcis10 留社考。Problem Setter:zenixls2
2021.03.13 Update: Added LATEX by FHVirus

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1