1312 . 家族

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

93.6% (280/299)

Submission's AC Ratio

42.1% (461/1096)

Tags

TFcis X-TFcis

Description

義大利黑手黨內有許多家族，家族定義如下：

有 n 個黨員，依名次為 1∼n

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

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

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

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

要你找出其首領

Input Format

本題有多組測資

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

其中 m 代表有幾組關係，m≤n≤10000

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

最後，輸入 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
Submit
Back to Top