丹妮莉丝（Khaleesi）已扬帆起航前往君临城。她拥有三条巨龙和数以万计的军队，势不可挡。船队正逐渐靠近君临城，她想要开始规划进攻。

进攻计划是将军队分为左右两翼。但有一个问题，丹妮莉丝的士兵来自非常不同的背景，其中一些人存在敌对关系，无法相处（比如马泰尔家族和提利尔家族），因此他们不能被分在同一个侧翼。

丹妮莉丝了解所有的敌对关系，并试图解决其中的一部分。然而，有些敌对关系很难解决，她必须处理它们。她想检查如果某些敌对关系未被解决，是否可以将士兵分为两个侧翼，使得没有两个不和的士兵在同一个侧翼中。你能帮助丹妮莉丝规划她的进攻，以坐上铁王座吗？

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量（$1 \le T \le 10$）。

每个测试用例以一行包含三个空格分隔的整数开始：

• $N$：士兵人数（$1 \le N \le 40,000$）
• $E$：敌对关系数量（$1 \le E \le 40,000$）
• $Q$：查询数量（$1 \le Q \le 40,000$）

接下来有 $E$ 行，每行包含两个空格分隔的整数 $A$ 和 $B$，表示士兵 $A$ 和 $B$ 不能在同一个侧翼（$1 \le A, B \le N$）。

接下来有 $Q$ 行，每行包含两个空格分隔的整数 $C$ 和 $D$，表示编号在 $[C, D]$ 范围内的所有敌对关系都无法解决（$1 \le C, D \le E$）。

输出格式

对于每个测试用例，打印 $Q$ 行，其中第 $i$ 行表示第 $i$ 个查询的答案。如果军队无法分为两个侧翼，则该行应包含 "-1 -1"（引号仅为说明）；否则，输出两个侧翼的大小，以单个空格分隔。如果有多种有效的分配方式，请打印使第一侧翼人数最多的那种。

样例

输入格式 1

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

输出格式 1

-1 -1
-1 -1
6 3
7 2
7 2
8 1