CF723E One-Way Reform

在 Berland 有 $n$ 个城市和 $m$ 条双向道路，每条道路连接两个城市。已知任意一对城市之间至多有一条道路相连，并且没有连接自身的道路。可能存在某些城市间无法仅通过这些道路到达。 公路部长决定改革，将全国所有道路变为有向道路，即每条道路只能单向通行。部长想要最大化满足如下条件的城市数量：对于这些城市，起点为该城市的道路数等于终点为该城市的道路数。

第一行包含一个正整数 $t$（$1 \leq t \leq 200$）——表示测试数据组数。 每组测试数据的格式如下。第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 200$，$0 \leq m \leq n\cdot(n-1)/2$）——表示城市数和道路数。 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示一条连接城市 $u$ 和城市 $v$ 的道路。保证没有自环和重边。可能存在两城市之间无法通过道路互达的情况。 保证所有测试数据中，总城市数不超过 $200$。 请注意，对于 hack 数据，你只能使用含有一个测试集的数据，即 $t$ 必须等于 $1$。

对于每组测试数据，输出最大化满足题目要求的城市数量，即起点和终点道路数相等的城市个数。 接下来输出 $m$ 行，描述每条有向道路的方向。每行输出两个整数，先输出起点城市编号，再输出终点城市编号。如果有多种方案，输出任意一种即可。每组测试中可以以任意顺序输出道路，但每条道路只能输出一次。

由 ChatGPT 5 翻译