无向图是图论中的一个基本概念，图论是数学和计算机科学的一个分支。它是一种数据结构，表示由无方向的边连接的顶点集合。换句话说，在无向图中，如果存在一条从顶点 $u$ 到顶点 $v$ 的边，那么也存在一条从顶点 $v$ 到顶点 $u$ 的边。我们使用一个二元集合 $\{A, B\}$ 来表示这样一条无向边。如果任意两点之间最多只有一条边，则该无向图是简单图。

在图论中，连通分量是图中的一组顶点和边，在其中你可以通过沿着一系列边从任意顶点到达任何其他顶点。桥是无向图中的一条边，如果将其删除，图中的连通分量数量将会增加。

桥是图分析中的重要概念，在网络设计、容错和连通性分析中有着实际应用。它们通常用于识别网络中的脆弱点，在这些点上，删除单条边可能会导致某些组件被孤立或连通性中断。识别图中的桥可以使用各种算法来完成，这些算法可以检测这些关键边，并帮助分析网络或系统的鲁棒性和结构。

你有一个简单无向图，其顶点集和边集分别为 $V = \{1, 2, \dots, n\}$ 和 $E = \{\{u_1, v_1\}, \dots, \{u_m, v_m\}\}$。你的朋友 Flora 要求你依次从图中删除边 $e_1, e_2, \dots, e_q$，并在每次删除后报告图中剩余的桥的数量。请编写一个程序来生成该报告。

输入格式

第一行包含三个空格分隔的非负整数 $n$、$m$ 和 $q$。$n$ 是图的顶点数。$m$ 是图的边数。$q$ 是要删除的边数。

接下来的 $m$ 行中，第 $i$ 行包含两个空格分隔的正整数 $u_i$ 和 $v_i$，表示 $E$ 的第 $i$ 个元素。

然后是 $q$ 行。其中的第 $j$ 行包含两个空格分隔的正整数 $x_j$ 和 $y_j$，表示第 $j$ 条被删除的边 $e_j$ 为 $\{x_j, y_j\}$。

输出格式

输出 $q$ 行。第 $k$ 行应包含一个整数 $b_k$，表示删除 $k$ 条边后图中桥的数量。

数据范围

• $1 < n \le 200000$
• $1 \le m \le \min \left(200000, \binom{n}{2}\right)$
• $1 \le q \le m$
• 表示边 $\{u, v\}$ 有两种方式：u v 和 v u。
• $\{x_i, y_i\}$ 必须是 $E$ 中的一条边。
• 没有边会被重复删除。

样例

输入样例 1

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

输出样例 1

0
2
1
3
2