题目描述

给定一张无向图，图中有 $n$ 个点和 $m$ 条边。接下来会发生 $k$ 个事件，事件有两种类型：

1. 在点 $a$ 与点 $b$ 之间新建一条边；
2. 删除点 $a$ 与点 $b$ 之间已有的一条边。

你的任务是：输出每个事件发生后，图中的连通块数量。

注意：还需要先输出第一个事件发生前，初始图中的连通块数量。

输入格式

第一行包含三个整数 $n,m,k$，分别表示点数、初始边数和事件数。

接下来 $m$ 行，每行包含两个整数 $a,b$，表示初始图中存在一条连接点 $a$ 与点 $b$ 的无向边。

保证任意两个点之间至多有一条边。

接下来 $k$ 行，每行形如：

t a b

其中：

• $t=1$ 表示在点 $a$ 与点 $b$ 之间新建一条边；
• $t=2$ 表示删除点 $a$ 与点 $b$ 之间已有的一条边。

保证：

• 新建边时，点 $a$ 与点 $b$ 之间当前不存在边；
• 删除边时，点 $a$ 与点 $b$ 之间当前存在边。

输出格式

输出 $k+1$ 个整数：

• 第一个整数表示第一个事件发生前，初始图中的连通块数量；
• 接下来 $k$ 个整数依次表示每个事件发生后，图中的连通块数量。

整数之间用空格分隔。

数据范围

样例输入

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

样例输出

2 2 2 1

样例解释

初始时有边 $(1,4),(2,3),(3,5)$，连通块为：

• $\{1,4\}$；
• $\{2,3,5\}$。

因此初始连通块数量为 $2$。

之后依次处理事件：

1. 加入边 $(2,5)$，这两个点本来已经在同一个连通块内，连通块数量仍为 $2$；
2. 删除边 $(3,5)$，由于仍可通过边 $(2,5)$ 连接，连通块数量仍为 $2$；
3. 加入边 $(1,2)$，两个原本不同的连通块被合并，连通块数量变为 $1$。

说明

本题要求处理动态图的连通块数量，边会被动态加入和删除。常见做法包括离线处理、线段树分治加可回滚并查集等。

时间与空间限制

• 时间限制：1.00 s
• 空间限制：512 MB