[IOI Camp Judge 53]鋪路問題 (題目備份)

IOI Camp Judge是暫時性的，因此在這裡做題目備份
題解在這裡，我也很克難的寫出了動態樹做法

鋪路問題

Time Limit: 3s

Description

你是一個國家的交通部長，你們國內總共有 N 座城市，城市間總共有 M 條道路，每條道路都爲雙向通行，但有些城市卻無法透過現有的道路到其他城市，而對於可以兩兩透過道路通往彼此的城市，我們稱爲城市群。如果一個城市群在加入其他城市後，不再是一個城市群，則稱之爲極大城市群。而這些道路中，又有一些道路是特別重要的，我們稱爲重要道路，重要道路的定義爲：如果把重要道路拔除，則國家內的極大城市群數量會增加。

身爲交通部長，你想改善國內的交通狀況，因此，你決定再建造 K 條道路，而且你想知道新建造的這些道路對現有交通狀況的影響，因此，你決定找出每建造一條道路後，國內總共的重要道路數。

Input Format

第一行有一個正整數 T，代表總共有幾筆測試資料。每筆測試資料第一行包含兩個正整數 N,M，代表國內的城市數以及現有的道路數。接下來包含 M 行，每行兩個正整數 ui,vi，代表存在城市 ui 到城市 vi 的雙向道路。接下來一行包含一個正整數 K，代表預計新建造的道路數。接下來包含 K 行，每行兩個正整數 ui,vi，代表新建造的雙向道路連接城市 ui 及城市 vi。

• 1≤T≤10
• 1≤N,K≤105
• 0≤M≤105
• 1≤ui,vi≤N

Output Format

對於每筆測試資料，請輸出 K 行，每行一個整數，代表每建造完一條道路後，國內的重要道路數。

Sample Input

1
3 0
3
1 2
2 3
1 3

Sample Output

1
2
0