← 返回题目列表

Codeforces · 723/E

E. 单向改革

中文机器翻译题面 查看原题

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