题目描述

愉快的周末到了，小理和他的 $N-1$ 个朋友买了 $M$ 个游戏，游戏编号从 $1$ ~ $M$。每个游戏都是多人游戏，他们打算周末一起打游戏。

小理的每个朋友都决定好了要玩哪一款游戏（会有一组人打同一款游戏），并且每人手上都有一台游戏机，这种游戏机可以通过特定的游戏机连接线连接起来。

但是，他们面临着一个问题：目前没有一个朋友的游戏机是互相连接的。所以它们必须用可用的游戏机连接线连接起来。小理决定依次使用第 $i$ 条连接线把他的朋友 $u_i$ 和 $v_i$ 的游戏机连接起来。也就是说，假设有 $Q$ 条连接线，小理只能先使用第一条，然后使用第二条，然后使用第三条。。。最后使用第 $Q$ 条。

一个游戏能开始的条件是所有玩这个游戏的朋友的游戏机都被连接起来（如果不是直接连接的话，那么就必须存在一条连接它们的路径）。他们希望尽快开始比赛。

在每个游戏中，找出在添加了第几条连接线之后能开始游戏。如果在一个游戏中只有一个人玩，则输出 $0$（因为他立马可以开始游戏）。如果不存在，则输出 $-1$。

输入格式

输入共 $Q+2$ 行。

第一行包含三个整数 $N$，$M$，$Q$。

第二行给 $N$ 个用空格分隔的整数，第 $i$ 个整数代表第 $i$ 个朋友想玩的游戏。

接下来的 $Q$ 行，每行两个整数 ($u$,$v$)，代表电线 $i$ 连接的两个人的电脑。

输出格式

对于每个游戏，输出一个整数，表示添加了第几条连接线之后能开始游戏，每行以换行符结束。

样例输入输出

样例输入

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

样例输出

3
4

数据范围

对于 $100%$ 的数据，保证 $1 \le N,M \le 10^{5},0 \le Q \le 10^{5}$。

样例解释

第一个游戏有两个人参加（$1$，$5$），在添加了第三条电线之后他们电脑互相连接。

第二个游戏三个人参加（$2$， $3$， $4$），在添加第四条电线之后他们电脑互相连接。