命定将焚的虹光
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
又到了举办夏日祭典的时候啦！这次祭典一共开设了 n 个摊位，有 m 条无向道路连接着摊位。由于 Naganohara Yoimiya 十分节省材料，因此不会出现两条道路连接某一对摊位，也不会出现某一条道路连接某个摊位和它自己。
为了丰富参加祭典的人们在摊位之间来回时的体验，Yoimiya 在每条道路上都设置了一些装饰品。
为了能够让人们一次性欣赏完 Yoimiya 设置的装饰，Yoimiya 希望存在一种方案，从某个摊位出发，每次沿着连接当前摊位和另一个摊位的一条道路走到另一个摊位，如此走遍所有的道路恰好一次，最后回到出发的摊位。这里，一个摊位可以经过多次，但每条道路都必须经过恰好一次。
现在的道路设计方案可能不满足条件，为此，Yoimiya 可以添加若干条道路，但不能删除已有的道路，也不能和已有的道路重合，使得添加道路后的设计方案满足 Yoimiya 的条件，即存在一种方案，从某个摊位出发，每次沿着连接当前摊位和另一个摊位的一条道路走到另一个摊位，如此走遍所有的道路恰好一次，最后回到出发的摊位。
Yoimiya 的材料不多了，因此添加的道路数量不能超过 2n−1 条。请你为她设计这样的一种方案，或者告诉她这是不可能做到的。
Input Format
本题有多组数据。第一行一个正整数 T 表示数据组数。对于每组数据：
第一行两个正整数 n,m，表示摊位的数量和道路的数量。
接下里 m 行，每行两个正整数 u,v，表示一条道路。
Output Format
对于每组数据：
如果无解，输出一行一个 -1。
否则，先输出一个数 k 表示你添加的道路个数，你需要保证 0≤k≤2n−1。
接下来 k 行，每行两个正整数 u,v 表示你添加的一条道路。
你需要保证 u=v，且 (u,v) 这条道路当前不存在。
5
4 2
1 4
2 3
4 5
1 2
1 3
1 4
2 3
2 4
4 4
1 2
2 3
3 4
4 1
6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6
5 02
1 3
2 4
-1
0
-1
5
1 2
2 3
3 4
4 5
1 5Hint
数据范围
对于所有数据，1≤n,∑n≤106,0≤m,∑m≤1.1×106,1≤T≤40000。
| 测试点编号 | 数据范围 | 特殊性质 |
|---|---|---|
| 1∼2 | n≤6 | 无 |
| 3 | ∑n≤100 | AB |
| 4,5 | ∑n≤100 | B |
| 6 | ∑n≤100 | A |
| 7,8 | ∑n≤100 | 无 |
| 9,10 | ∑n≤2000 | B |
| 11,12,13 | ∑n≤2000 | 无 |
| 14,15,16 | ∑n≤106 | B |
| 17,18,19,20 | ∑n≤106 | 无 |
- 特殊性质 A：对于每个摊位，和它直接相连的摊位个数都是偶数。
- 特殊性质 B：n 为奇数。
样例解释
- 为了方便选手调试，Yoimiya 在不同组数据之间添加了空行；实际数据中没有这个空行。
对于第一组数据，原本的道路设计中不存在这样符合 Yoimiya 要求的方案。
新增两条边 (1,3),(2,4) 后，就存在一种方案 1→2→3→4→1。
对于第二组数据，唯一可以加的边是 (3,4)，然而不论加不加这条边，都不存在 Yoimiya 要求的方案。
对于第三组数据，不需要加任何边就存在一种方案 1→2→3→4→1。
下发文件中提供了 checker.cpp 和 testlib.h，你可以用它们测试你的程序。