P6954 [NEERC 2017] Connections

艰难的时刻即将降临到 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} eq y_{i})$。保证可以仅使用现有道路从任何城市到达任何其他城市。对于每对城市 $(x , y)$，最多只有一条从城市 $x$ 到城市 $y$ 的道路，以及最多一条从城市 $y$ 到城市 $x$ 的道路。保证解的存在。单个输入中所有测试用例的 $m$ 之和不超过 $100 000$。

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

时间限制：3 秒，内存限制：512 MB。 题面翻译由 ChatGPT-4o 提供。