a347. TOI 2021/03 潛力組：航班

題目描述

有 N 個國家及 M 個雙向航班。兩個國家除了直接搭機，也可以透過其他國家轉機互相到達。疫情期間會陸續取消一些航班；請依操作順序回答：目前從指定國家出發，還能到達多少個其他國家？

輸入格式

第一行為 N、M，其中 1 ≤ N ≤ 4×10^5，0 ≤ M ≤ 10^6。國家編號為 1 到 N。 接著 M 行，第 i 行為 A_i、B_i，表示編號 i 的雙向航班連接這兩國；1 ≤ A_i,B_i ≤ N，A_i ≠ B_i。相同兩國間可以有多個航班，航班編號由 1 開始。

下一行為操作數 Q，1 ≤ Q ≤ 10^6。接著 Q 行，每行是一種操作：

• 1 p：取消編號 p 的航班，1 ≤ p ≤ M。每個航班保證不會重複取消。
• 2 Cq：查詢目前從國家 Cq 可到達的其他國家數，1 ≤ Cq ≤ N。

輸出格式

每遇到一次類型 2 操作，輸出一行整數，表示當時能到達的國家數，不計算出發國家本身。類型 1 操作不輸出。

原題分組限制

10 分：N≤10^3、M≤10^4、Q≤10^4。10 分：所有取消操作都在詢問之前。20 分：N≤10^5、M=N−1、Q≤4×10^5，i≠1 時 A_i=B_(i−1)，且初始所有國家互通。20 分：N≤10^5、M=N−1、Q≤4×10^5，且初始所有國家互通。40 分：無額外限制。

範例 1

輸入：

3 2
1 2
2 3
3
2 1
1 2
2 1

輸出：

2
1

範例 2

輸入：

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

輸出：

0

來源

TOI 2021 年 3 月練習賽潛力組，依官方 PDF 整理。

官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202103/Flight.pdf

標籤：TOI 歷屆