a279. TOI 2025/11 潛力組：串珠吊飾

題目描述

一個吊飾由 N 顆串珠和 M 條線組成，串珠編號為 0 到 N−1，所有串珠原本互相連通。第 0 顆固定在掛鉤上。

每筆詢問指定剪斷一條既有的線，與第 0 顆不再連通的串珠就會掉落。請計算仍掛在吊飾上的串珠數。各詢問彼此獨立，都從完整吊飾開始，只剪指定的一條線。

輸入格式

第一行為 N、M、Q。接著 M 行各有 S、T，表示兩串珠間有一條線。再接著 Q 行各有 Qs、Qt，指定本次剪斷的線。

• 3 ≤ N ≤ 50000，2 ≤ M ≤ 50000，1 ≤ Q ≤ M
• 每條原始線滿足 0 ≤ S < T < N，不重複
• 圖形連通，詢問的線保證存在。

輸出格式

對每筆詢問輸出一行整數，表示與掛鉤仍相連的串珠數，包含第 0 顆。

來源

TOI 2025 年 11 月潛力組〈串珠吊飾〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202511/BeadedCharm.pdf