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

板块: Advanced Techniques

时限: 1.00 s ｜ 内存: 512 MB

题目描述

考虑一个由 $n$ 个节点和 $m$ 条边组成的无向图。会发生两类事件：

1. 在节点 $a$ 和 $b$ 之间新建一条边。
2. 移除节点 $a$ 和 $b$ 之间已存在的一条边。

你的任务是在每次事件后报告连通块的数量。

输入

第一行有三个整数 $n$、$m$ 和 $k$：节点数量、边数量与事件数量。

之后有 $m$ 行描述边。每行有两个整数 $a$ 和 $b$：节点 $a$ 与节点 $b$ 之间有一条边。任意两个节点之间最多只有一条边。

然后有 $k$ 行描述事件。每行形如「$t$ $a$ $b$」，其中 $t$ 为 1（新建一条边）或 2（移除一条边）。新边总是在两个原本没有边相连的节点之间创建，且只有已存在的边才会被移除。

输出

输出 $k+1$ 个整数：先是第一次事件前的连通块数量，其后是每个事件后的新连通块数量。

数据范围

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

样例输入

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

样例输出

2 2 2 1