72 . Digital Firends 3
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
1 2
2 3
2 4
2 3 5
Sample Output 1
Sample Input 2
2 1
9 3
9 5
1 2 3 9
Sample Output 2
Sample Input 3
2 5
7 1
4 5
7 2
5 6
1 7
1 2 3 4 5 6 8
Sample Output 3
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 | 1000 | 65536 | 65536 | |
| 2 | 1000 | 65536 | 65536 | |
| 3 | 1000 | 65536 | 65536 | |
| 4 | 1000 | 65536 | 65536 | |
| 5 | 1000 | 65536 | 65536 | |
| 6 | 1000 | 65536 | 65536 | |
| 7 | 1000 | 65536 | 65536 | |
| 8 | 1000 | 65536 | 65536 | |
| 9 | 1000 | 65536 | 65536 | |
| 10 | 1000 | 65536 | 65536 | |
| 11 | 1000 | 65536 | 65536 | |
| 12 | 1000 | 65536 | 65536 | |
| 13 | 1000 | 65536 | 65536 | |
| 14 | 1000 | 65536 | 65536 | |
| 15 | 1000 | 65536 | 65536 |