北大餐饮综合楼开业了！

小 F 是一只有学识的鸡，为了不被餐饮综合楼四楼的小火锅涮掉，它打算向愚蠢的人类展示一些技能。

人类总共有 $T$ 次询问，每一次给了一张 $n$ 个点 $m$ 条边的图 $H=(V_H,E_H)$。而小 F，同构判定鸡，每一次会回答一张图 $G=(V_G, H_G)$，满足以下条件：

1. 点数 $|V_G|\le N$；
2. 边数 $|E_G|\ge M$；
3. $H$ 不是 $G$ 的子图，即：无法通过删除 $G$ 的点和边并重新标号后得到 $H$。

人类不知道小 F 的高超的图同构水平，于是给定的图 $H$ 会满足一些特殊性质（见数据范围）。

而小 F 觉得这题太简单了，于是把问题交给了你。

输入格式

第一行两个非负整数 $T, type$，表示数据组数和测试点的序号。若 $type=0$，则表示该组数据为样例，不会出现在评测数据集合中。也就是说对于所有评测数据，满足 $1 \le type \le 6$。

对于每一组数据，第一行 $n,m$ 两个非负整数，含义同题面。

接下来 $m$ 行，每行两个整数 $u_i,v_i$，表示图 $H$ 中的一条边。保证没有重边和自环。

最后一行两个整数 $N,M$，表示对图 $G$ 的点数和边数的限制。

输出格式

对于每一组数据，第一行两个正整数 $n',m'$，表示你构造的图 $G$ 的点数和边数。

接着有 $m'$ 行，每行两个正整数 $x_i, y_i$ 表示图 $G$ 中的边。

你需要保证图 $G$ 中不存在重边与自环，否则你的答案会被判定为错误。

样例数据

样例输入

1 0
4 3
1 2
1 3
3 4
4 0

样例输出

4 0

样例解释

显然 $H$ 不是空图 $G$ 的子图。

数据范围

本题共 $6$ 个测试点，以下为每个测试点的信息：

测试点 1 到测试点 4 使用 special judge 1 进行测评，输出应完全符合题目条件才能得到所有的分数。

测试点 1（$5\%$）：$H$ 为 $3$ 个点的完全图；$N \le 100$，$M = [N^2/4]$。$[]$ 为下取整符号，下同。

测试点 2（$10\%$）：$H$ 为完全图，且 $n \le 10$；$n \le N \le 100$，$M = \left[\left(1-\frac1{n-1}\right) \cdot N^2/2\right]-1$。

测试点 3（$10\%$）：$H$ 为 $K(2, 2)$（左侧 $2$ 个点、右侧 $2$ 个点的完全二分图，下同）；$50 \le N \le 2000$，$M = 2N$。

测试点 4（$15\%$）：$H$ 为 $K(2, 2)$；$N \le 2000$，且 $N$ 能表示成一个奇质数的平方，$M = [N(\sqrt N-1)/2]$。

测试点 5 和测试点 6 满足 $T=1$，使用 special judge 2 进行测评。输出应完全符合题目条件才能得分。假设你给出的方案的边数为 $m'$，你程序的得分为 $\left\lfloor 30\times\left(1-0.5\left(\frac{3M}{m'}-1\right)\right)\right\rfloor$。也就是说，只有 $m' \ge 3M$ 的方案才能拿到满分。

测试点 5（$30\%$）：$H$ 为 $K(2, 2)$；$N=2850$，$M=24300$，$3M=72\,900$；

测试点 6（$30\%$）：$H$ 为 $K(3, 3)$；$N = 343 = 7^3$，$M=2350$，$3M=7050$。

对于所有测试点，有 $1 \le T \le 10$，$N \ge n > 2$。