程式解題社網站 程式解題社網站上線了！
NTUCPC OJ 現在支援 Rust ！
NTUCPCPC 2026 初賽 & 決賽題目已公開！ 連結
YTP 2026 題目已公開！ 連結
1488 . 資訊之林
TopCoder
Tags
Description
YTP 國在一座小島上，長滿了一種稱為「資訊之芽」的植物，隨著時間的流逝，「資訊之芽」逐漸長成了「資訊之樹」，這些樹的枝葉開始會碰到彼此。
而 YTP 國的島民習慣使用刀耕火種的方式來種植，但他們的技術卻不熟練。
島上總共有 $n$ 棵樹，形成一張共有 $n$ 個點 $m$ 條邊的無重邊無自環無向圖，其中每棵樹是一個點，如果兩個點碰在一起，則他們之間有一條無向邊。
對於每一條邊的兩個端點，我們說這兩個點相鄰。
並且有 $k$ 棵樹不小心被點燃了，假設第 $i$ 棵樹在時刻 $t_i$ 被點燃，則他會在時刻 $t_i+1$ 把所有相鄰但還沒被點燃的樹點燃。
若某棵樹 $j$ 在某個時刻 $t_j$ 被點燃，或在同一時間被點燃多次，
造成的結果都只是樹 $j$ 在時刻 $t_j$ 開始就是被點燃的狀態，
時刻 $t_j$ 之後就算又被點燃也不會改變狀態。
現在有 $q$ 個慌亂的島民想要知道特定的兩棵樹 $a,b$ 最晚在何時還連通，
其中連通的意思是可以找到一個包含起終點的樹的序列，使得序列中連續的兩棵樹都相鄰，且序列中的每棵樹在時刻 $x$ 當下都還沒被點燃（在時刻 $x$ 被點燃的話就不滿足這個條件）。
對於每一個島民，回答他時刻 $x$ 最大是多少時，詢問的兩棵樹是連通的。
最初時刻 $0$ 時所有的樹都還沒被點燃。
若詢問的兩棵樹 $a,b$ 在時刻 $0$ 就不連通，回答 $-1$。
若詢問的兩棵樹 $a,b$ 無論經過多久都會連通，回答 $-164253$。
Input Format
輸入第 $1$ 行有四個正整數 $n, m, k, q$ 依序以一個空格隔開。
第 $2$ 行到 $m+1$ 行每行有兩個正整數 $a, b$ 以一個空格隔開，代表 $a, b$ 兩棵樹之間有一條邊，兩棵樹相鄰。
第 $m+2$ 行到第 $k+m+1$ 行每行有兩個正整數 $i, t_i$ 依序以一個空格隔開，代表第 $i$ 棵樹在時刻 $t_i$ 被點燃。
第 $k+m+2$ 行到 $q+k+m+1$ 行每行有兩個正整數 $a, b$ 以一個空格隔開，代表有一個島民要詢問 $a, b$ 兩棵樹到何時還會連通。
- $2 \leq n \leq 10^ 5$
- $1 \leq m \leq 10^ 5$
- $1 \leq a, b \leq n$ 且 $a \neq b$
- $m$ 條邊中沒有重邊，詢問則不保證沒有重複。
- $1 \leq k \leq n$
- $1 \leq q \leq 10^ 5$
- $1 \leq t_i \leq 10^ 5$，其中 $i$ 是一開始給定被點燃的樹，總共 $k$ 棵，且這 $k$ 個樹相異
Output Format
對於輸入的最後 $q$ 行，每行回答一個整數，代表時刻 $x$ 最大是多少時，詢問的兩棵樹是連通的。
若詢問的兩棵樹 $a,b$ 在時刻 $0$ 就不連通，回答 $-1$。
若詢問的兩棵樹 $a,b$ 無論經過多久都會連通，回答 $-164253$。
Sample Input 1
4 2 1 3 1 2 3 4 1 8 1 2 1 3 3 4
Sample Output 1
7 -1 -164253
Hints
範測 $1$ 解釋：
第一筆詢問樹 $1$ 在時刻 $8$ 被點燃，故答案是 $7$。
第二筆詢問兩樹不連通。
第三筆詢問兩樹永遠連通。
Problem Source
2026 YTP 高中組初賽 p8
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測試資料 | 0 |
| 2 | 0~8 | $n, m, q, t_i \leq 500$ | 4 |
| 3 | 0, 9~16 | $k=1$ | 8 |
| 4 | 0~24 | 無額外限制 | 8 |