题目描述

雅娜没能为这道题编出一个故事（即便有 ChatGPT 的帮助也不行）。因此你将直接看到它朴素的数学表述。

给定一个有 n 个点、m 条边的图 G。请先判断这个图是否是二分图；如果不是，输出 -1。

否则，你还会得到一个长度为 q 的边序列 (u_j,v_j)。你需要按输入顺序把这些新边一条一条加入图中，并找出图第一次不再是二分图的时刻。若始终没有这样的时刻，则输出 -2。

我们称图 G 是“二分图”，当且仅当它的所有顶点可以被划分为两个集合，并且每条边都连接两个不同集合中的顶点。

请编写程序 bipartite 来解决这个问题。

输入格式

标准输入第一行给出 n、m、q，分别表示图中顶点数、原始图中的边数，以及后续将被加入图中的边数。

接下来 m 行，每行给出一对整数 (u_i,v_i)，表示原始图中的一条边。

接下来 q 行，每行给出一对整数 (u_j,v_j)，表示之后要加入图中的一条边。它们在输入中出现的顺序，正是实际加入图中的顺序。

输出格式

输出一个整数：

• -1：表示原始图在加入任何新边之前就不是二分图；
• -2：表示原始图是二分图，且后续加入的所有边都不会破坏其二分性；
• x：表示加入第 x 条新边时，图第一次失去二分性。

数据范围

• 1 ≤ n ≤ 2 × 10^5
• 1 ≤ m, q ≤ 4 × 10^5
• 对所有 1 ≤ i ≤ m 和 1 ≤ j ≤ q，都有 1 ≤ u_i, v_i, u_j, v_j ≤ n
• 图中允许出现重边和自环
• 在大约 33% 的测试中，q = 0

样例 #1

输入 #1

3 3 0
1 2
1 3
2 3

输出 #1

-1

说明 #1

可以证明，该图不是二分图。

样例 #2

输入 #2

3 0 3
1 2
1 3
2 3

输出 #2

3

说明 #2

加入最后一条边后，图失去了二分性。

样例 #3

输入 #3

8 5 6
1 5
5 1
6 7
2 4
2 7
6 8
8 2
4 3
3 7
6 2
4 6

输出 #3

5

说明 #3

图中标记为 0 的边表示原本就在图中的边；标记为正整数的边表示后续加入的边，且数字就是它们被加入的顺序。

样例 #4

输入 #4

8 4 5
1 3
2 7
8 5
4 6
3 7
2 5
4 5
6 8
8 1

输出 #4

-2

说明 #4

这里图在整个过程中始终保持二分图。

原题在该样例下同样给出了对应示意图。