Byteland 正在经历艰难时期。量子计算正成为主流，Qubitland 即将占领 Byteland。主要问题是 Byteland 没有足够的资金来应对这场战争，因此 Byteland 的国王 Byteman 0x0B 决定改革其道路系统以减少开支。

Byteland 有 $n$ 个城市，由 $m$ 条单向道路连接，并且可以通过这些道路从任意城市到达其他任何城市。没有两条道路在城市之外相交，也不存在其他道路。顺便提一下，这些道路是单向的，因为每条道路都有一个只能单向通过的半程障碍。这些障碍旨在迫使敌人在选择错误道路时浪费时间。

即将进行的道路改革的想法是废弃一些道路，使得最终恰好剩下 $2n$ 条道路。国王的顾问认为，保持从任意城市到达其他任何城市的能力应该就足够了。（也许更少的道路也足够？他们并不确定。）问题在于如何选择要废弃的道路。Byteland 的每个人都知道，只有你能解决这个问题。

输入格式

输入包含多个测试用例。输入的第一行包含测试用例的数量。

每个测试用例的第一行包含 $n$ 和 $m$ —— 分别表示城市数量和道路数量（$n \ge 4, m > 2n$）。接下来的 $m$ 行，每行包含两个数字 $x_i$ 和 $y_i$，表示一条从城市 $x_i$ 到城市 $y_i$ 的道路（$1 \le x_i, y_i \le n, x_i \neq y_i$）。保证仅使用现有道路即可从任意城市到达其他任何城市。对于每一对城市 $(x, y)$，最多只有一条从城市 $x$ 到城市 $y$ 的道路，且最多只有一条从城市 $y$ 到城市 $x$ 的道路。保证解一定存在。单个输入中所有测试用例的 $m$ 之和不超过 $100\,000$。

输出格式

对于每个测试用例，输出 $m - 2n$ 行。每行描述一条应该废弃的道路。以与输入相同的格式打印道路：源城市编号和目标城市编号。输出中道路的顺序无关紧要，但输入中的每条道路在输出中最多只能出现一次，且输出中的每条道路必须存在于输入中。在废弃道路后，仍然必须能够从任意城市到达其他任何城市。

样例

输入 1

1
4 9
1 2
1 3
2 3
2 4
3 2
3 4
4 1
4 2
4 3

输出 1

1 3