994 . 派對

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc
有人要寫 p6 嗎 > <

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

ntucpc-speedrun2

Description

完整題本 PDF：中文、英文、馬來文。

NTU 市是一個熱愛運動的城市，城市中的市民個個都是運動好手。作為傳統，NTU 市每年都會舉辦一場全市運動會，來決定誰是全城市最強的運動員。為了慶祝，在運動會中獲得總冠軍的人會舉辦一場派對，並邀請所有他的朋友來參加，同時，他會允許他的朋友邀請任意數量自己的朋友來參加派對。

作為 NTU 市的市民，小李好奇，假設只有慶祝派對的主人和被邀請允許出現的人才會出現在派對，那麼，如果知道全城市中哪些人彼此是朋友，以及全市運動會的總冠軍是誰，最多會有多少人出現在派對上呢？

Input Format

輸入第一行包含三個正整數 $N, M$ 和 $W$，代表 NTU 市的市民總數和城市中，總共有幾對朋友關係，並且第 $W$ 位市民是運動會的總冠軍。

接下來有 $M$ 行輸入，第 $i$ 行包含兩個正整數 $x_i, y_i$，代表第 $x_i$ 位市民和第 $y_i$ 位市民是朋友。

  • $1 \leq N \leq 2 \times 10 ^ 5$
  • $0 \leq M \leq 2 \times 10 ^ 5$
  • $1 \leq x_i, y_i, W \leq N$
  • $x_i \neq y_i$
  • $\forall 1 \leq i, j \leq M, i \neq j, (x_i, y_i) \neq (x_j, y_j)$ and $(x_i, y_i) \neq (y_j, x_j)$

Output Format

輸出一個正整數，代表派對上最多可能出現的人數。

Sample Input 1

5 5 1
1 2
2 3
2 4
3 5
4 5

Sample Output 1

4

Sample Input 2

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

Sample Output 2

5

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 2097152 65536
1 1000 2097152 65536
2 1000 2097152 65536
3 1000 2097152 65536
4 1000 2097152 65536
5 1000 2097152 65536
6 1000 2097152 65536
7 1000 2097152 65536
8 1000 2097152 65536
9 1000 2097152 65536
10 1000 2097152 65536
11 1000 2097152 65536
12 1000 2097152 65536
13 1000 2097152 65536
14 1000 2097152 65536
15 1000 2097152 65536
16 1000 2097152 65536
17 1000 2097152 65536
18 1000 2097152 65536
19 1000 2097152 65536
20 1000 2097152 65536
21 1000 2097152 65536
22 1000 2097152 65536
23 1000 2097152 65536
24 1000 2097152 65536
25 1000 2097152 65536
26 1000 2097152 65536
27 1000 2097152 65536
28 1000 2097152 65536
29 1000 2097152 65536
30 1000 2097152 65536
Submit
Back to Top