Berland有n个城市和m条双向道路,每条道路连接两个城市。众所周知,连接每对城市的道路不超过一条,也没有一条道路将城市与其本身连接起来。仅使用这些道路可能无法从一个城市到达另一个城市。
公路部长决定在贝尔兰进行一项改革,并对全国所有道路进行定向,即每条道路都是单向的。部长希望最大化城市数量,其中从城市开始的道路数量等于以城市结束的道路数量。
输入
第一行包含一个正整数 t (1 ≤ t ≤ 200) — 输入中测试集的数量。
每个测试集均按以下方式给出。第一行包含两个整数 n 和 m (1 ≤ n ≤ 200, 0 ≤ m ≤ n·(n - 1) / 2) - Berland 的城市数量和道路数量。
接下来的 m 行包含 Berland 道路的描述。每行包含两个整数 u 和 v (1 ≤ u, v ≤ n) - 相应道路连接的城市。保证无自环、多路。两个城市之间的道路可能没有路。
保证输入数据所有测试集中的城市总数不超过200个。
请注意,对于 hacks,您只能使用由一个测试集组成的测试,因此 t 应等于 1。
输出
对于每个测试集,打印此类城市的最大数量,使得从该城市开始的道路数量等于以该城市结束的道路数量。
在接下来的 m 行中打印定向道路。首先打印道路起点的城市编号,然后打印道路终点的城市编号。如果有多个答案,请打印其中任何一个。允许以任意顺序打印每次测试中的道路。每条路都应该打印一次。
示例
输入 #1
2 5 5 2 1 4 5 2 3 1 3 3 5 7 2 3 7 4 2
输出 #1
3 1 3 3 5 5 4 3 2 2 1 3 2 4 3 7