User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

62.5% (5/8)

Description

「請和我成為朋友」,所有人都認為這是件十分美好的事情,但是這是錯的!
朋友之間有存在著明確的地位關係,主導者和被主導者,勝者與敗者,如果想要活得有尊嚴的話,那就絕對不能成為敗者。

但是如果已經成為了敗者那就回天乏術了,只能互相用網路聊天的方式相互取暖。

現在有 $N$ 個敗者在網路上(敗者編號從 $1$ 開始),得到安慰的敗者,會去安慰有網路線直接連接且尚未被安慰的敗者。

這個網路上有 $M$ 條網路線互相連接,之後有 $Q$ 個詢問,請問敗者 $X$ 是誰去安慰他?(在最一開始,會給你指定一個敗者 $K$,他會得到會長的安慰,所以可以開始去安慰其他敗者)

Input Format

輸入共三部分。

第一部分有一行,共有 $4$ 個數字,代表 $N, M, Q, K$
$1 \leq K \leq N \leq 3 \cdot 10^ 5$
$0 \leq M \leq 3 \cdot 10^ 5 $
$Q < N$
第二部分有 $M$ 行,每一行有兩個數字,代表敗者 $X, Y$ 中間有網路線連接。
第三部分有一行,共有 $Q$ 個數字,代表 $Q$ 筆詢問。(詢問中不會詢問敗者 $K$ )

需要考慮重邊,但是不需要考慮環。

Output Format

輸出共有一行,共有 $Q$ 個數字,代表 $Q$ 筆詢問的答案。

若詢問的目標始終得不到安慰,請輸出 -1

Sample Input 1

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

Sample Output 1

4 2 -1

Sample Input 2

10 3 4 5
2 1
9 3
9 5
1 2 3 9

Sample Output 2

-1 -1 9 5

Sample Input 3

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

Sample Output 3

7 7 -1 5 2 5 -1

Hints

關於前傳故事,可以在賽後進入一下兩個連結,現在點擊傳送門對你的比賽是不會有幫助的喔!

Digital Firends 1
Digital Firends 2

這次的輸入有點多,請各位一定要會使用
ios::sync_with_stdio(0); cin.tie(0);
或是
scanf and printf


Q: 有方向的網路還是沒有方向的網路?
A: 無方向。

Q: 詢問的時間點為何?
A: 當所有安慰行動結束之後。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 10
2 2~14 $1 \leq N, M \leq 10^ 5$ 89
3 15 $1 \leq N, M \leq 3 \cdot 10^ 5$ 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 2
3 1000 65536 65536 2
4 1000 65536 65536 2
5 1000 65536 65536 2
6 1000 65536 65536 2
7 1000 65536 65536 2
8 1000 65536 65536 2
9 1000 65536 65536 2
10 1000 65536 65536 2
11 1000 65536 65536 2
12 1000 65536 65536 2
13 1000 65536 65536 2
14 1000 65536 65536 2
15 1000 65536 65536 3