Network Breakdown

题目描述

Syrjälä 的网络有 n 台计算机和 m 条它们之间的连接。网络由可以相互发送消息的计算机组件组成。 Syrjälä 的人没人理解这个网络是如何工作的。因此，如果一条连接断开，没人会修理它。在这种情况下，一个组件可能会被分成两个组件。 你的任务是在每次连接断开后计算组件的数量。

输入格式

第一行输入有三个整数 n, m 和 k：计算机的数量、连接的数量和故障的数量。计算机编号为 1,2,$\dots$,n。 之后有 m 行描述连接。每行有两个整数 a 和 b：计算机 a 和 b 之间有一条连接。每条连接都在两个不同的计算机之间，且任意两台计算机之间最多有一条连接。 最后有 k 行描述故障。每行有两个整数 a 和 b：计算机 a 和 b 之间的连接断开。

输出格式

在每次故障之后，输出组件的数量。

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

2 2 3

提示

$1 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le k \le m$ $1 \le a,b \le n$

标签: CSES1677|高级图论问题

来源

CSES1677|高级图论问题