网络扩建

题目背景

编程挑战赛组委会在布置比赛场地的网络。场地内有若干台交换机，其中一部分交换机之间已经铺设了网线，使得部分交换机形成了若干个互相连通的区域（称为「连通块」）。不同连通块之间目前无法通信，它们各自是孤立的。

组委会手上有一份备选网线的清单，共 $q$ 条。每条备选网线可以连接两台指定的交换机。一旦铺设一条备选网线且它两端的交换机原本不在同一个连通块内，这两个连通块就会合并为一个更大的连通块，从而减少一个孤立区域。如果两端已经在同一个连通块内，铺设这条网线不会改变任何东西（它是一条冗余线）。

题目描述

有 $n$ 台交换机，编号 $1 \sim n$。已经铺设了 $m$ 条网线，每条网线连接 $u_i$ 和 $v_i$。

现在有 $q$ 条备选网线，按顺序编号 $1$ 到 $q$，第 $i$ 条连接 $a_i$ 和 $b_i$。你必须按顺序考虑备选网线——即只能从第 $1$ 条开始，连续地铺设前 $k$ 条（$0 \le k \le q$），不能跳过任何一条。

你的目标是让所有交换机最终处于同一个连通块内（即任意两台交换机都可以通过若干条网线互相到达）。请问最少需要铺设多少条备选网线（即最小的 $k$）？如果即使把全部 $q$ 条备选网线都铺上也无法达成目标，请输出 $-1$。

输入格式

第一行三个整数 $n, m, q$（$1 \le n \le 10^5$，$0 \le m \le 2\times 10^5$，$1 \le q \le 2\times 10^5$）。

接下来 $m$ 行，每行两个整数 $u_i, v_i$（$1 \le u_i, v_i \le n$），表示一条已有网线。

接下来 $q$ 行，每行两个整数 $a_i, b_i$（$1 \le a_i, b_i \le n$），表示一条备选网线。

输出格式

一个整数，表示最少需要铺设的备选网线条数；若无法达成目标则输出 $-1$。

样例

样例 1

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

2

解释：已有网线形成了三个连通块 $\{1,2\}$、$\{3,4\}$、$\{5,6\}$。铺第 $1$ 条备选线 $(1,3)$ 后，前两块合并为 $\{1,2,3,4\}$，还剩 $2$ 个孤立区域。铺第 $2$ 条备选线 $(4,6)$ 后，$\{1,2,3,4\}$ 和 $\{5,6\}$ 合并，全场只剩 $1$ 个连通块，目标达成。答案为 $2$。注意第 $1$ 条备选线连接的是 $(1,3)$，实际上第 $1$ 条就合并了 $\{1,2\}$ 和 $\{3,4\}$。

样例 2

输入：
4 0 3
1 2
3 4
2 3

输出：
3

解释：初始没有已有网线，$4$ 台交换机各自孤立（$4$ 个连通块）。铺第 $1$ 条 $(1,2)$，剩 $3$ 块。铺第 $2$ 条 $(3,4)$，剩 $2$ 块。铺第 $3$ 条 $(2,3)$，所有交换机连通，目标达成。答案为 $3$。

样例 3

4 0 2
1 2
3 4

-1

解释：初始 $4$ 个孤立块。铺完 $2$ 条备选线后仍然有 $2$ 个连通块（$\{1,2\}$ 和 $\{3,4\}$），无法达成全场连通，输出 $-1$。