链接: https://cses.fi/problemset/task/1677

板块: Advanced Graph Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

Syrjälä 的网络有 $n$ 台计算机和 $m$ 条连接。网络由若干可以互相传递消息的计算机组件构成。

Syrjälä 没有人明白网络是如何工作的。因此，一旦某条连接断开，就没有人会去修复它。在这种情况下，一个组件可能会分裂成两个组件。

你的任务是在每次连接断开后，计算组件的数量。

输入

第一行包含三个整数 $n$、$m$ 和 $k$：计算机数量、连接数量和断线次数。计算机编号为 $1,2,\dots,n$。

接下来有 $m$ 行描述连接。每行包含两个整数 $a$ 和 $b$：表示计算机 $a$ 与 $b$ 之间有一条连接。每条连接连接两台不同的计算机，且任意两台计算机之间最多只有一条连接。

最后有 $k$ 行描述断开情况。每行包含两个整数 $a$ 和 $b$：表示计算机 $a$ 与 $b$ 之间的连接断开。

输出

每次断开后，输出组件的数量。

数据范围

$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$

样例输入

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

样例输出

2 2 3