L. 向日葵的坡道
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
「人啊，幸福吧！不沉溺在幸福中，也不对世界感到绝望，只是幸福地活下去！」
— 路德维希·维特根斯坦

你所看到的世界尽头的天空。

世界之界限的天空。

最尽头的天空。

我能不能够和你一起看呢？

在那里看着同一个世界的终结......

虽然不在同一片天空之下...... 却在同一片天空之下看着......

...... 我不时会思考这样的事情。

在回忆起......

回忆起那片向日葵前方的坡道时。

给定一个有向二分图（一个有向图，所有点可以被分为两类，同一类的点之间不存在边）。已知这个有向二分图的两个独立点集分别为 $$$A$$$ 和 $$$B$$$，且 $$$A$$$ 和 $$$B$$$ 的大小均为 $$$n$$$。

对点进行编号，$$$A$$$ 中的点从 $$$1$$$ 到 $$$n$$$，$$$B$$$ 中的点从 $$$n+1$$$ 到 $$$2n$$$。

在这个图中，所有的边均从 $$$A$$$ 中的某个点指向 $$$B$$$ 中的某个点，且不会有重边。

现在，请你为给定的有向二分图设计一种加边方案，使得该图成为强连通图，且加的边数最少。你只需要输出任意一种满足条件的方案即可。

请注意，不保证输入图连通。不要求加边后的图还是二分图，只要有强连通性质且边数最小即可。

Input

第一行输入一个正整数 $$$T$$$ ($$$1 \leq T \leq 10^4$$$)，表示测试用例数。

对于每组测试用例：

  • 第一行输入两个整数 $$$n$$$ ($$$1 \leq n \leq 10^6$$$) 和 $$$m$$$ ($$$0 \leq m \leq 2\cdot 10^6$$$)， 分别表示有向二分图两个点集的大小和图的边数。
  • 接下来 $$$m$$$ 行，每行输入两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u \leq n, n + 1 \leq v \leq 2\cdot n$$$)，表示有向二分图的一条边， 边的方向是从 $$$A$$$ 中的点 $$$u$$$ 指向 $$$B$$$ 中的点 $$$v$$$。

保证所有测试用例中的 $$$n$$$ 之和不超过 $$$10^6$$$，$$$m$$$ 之和不超过 $$$2\cdot 10^6$$$。

Output

对于每个测试用例，首先输出一行一个整数 $$$k$$$，表示需要添加的边数。

接着输出 $$$k$$$ 行，每行输出两个整数 $$$u$$$ 和 $$$v$$$，表示新增一条从 $$$u$$$ 指向 $$$v$$$ 的边。

如果有多种方案，你只需要输出其中一种合法方案即可。

Example
Input
3
1 0
1 1
1 2
2 3
1 3
1 4
2 3
Output
2
1 2
2 1
1
2 1
2
4 2
3 1
Note

对于第一组样例：

加边前
加边后

此时形成了强连通图。