TopCoder

Thumb fhvirus
FHVirus
$\huge{WHP}$

User's AC Ratio

95.4% (167/175)

Submission's AC Ratio

46.6% (270/580)

Tags

Description

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

有 $n$ 個黨員,依名次為 $1 \thicksim n$

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

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

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

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

要你找出其首領

Input Format

本題有多組測資

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

其中 $m$ 代表有幾組關係,$m \le n \le 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
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 (KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1