CF1912H Hypercatapult Commute

比特兰正在运行一种革命性的新型交通系统。这种系统既不需要道路，也不需要复杂的机械装置，只需要巨大的投石机。 系统的工作方式如下：比特兰有 $n$ 个城市。每个城市的市中心都有一台投石机。想要出行的人会被放进一个特殊的舱体，然后投石机会把这个舱体投送到另一个城市的市中心。每台投石机的威力都足以将舱体投送到任何其他城市，无论舱体里有多少乘客。唯一的问题是，给投石机充能需要很长时间，因此每台投石机每天只能使用一次。 乘客可能需要多次使用投石机。例如，如果乘客想从城市 $A$ 前往城市 $B$，他们可以先用投石机从 $A$ 到 $C$，再换乘另一台投石机从 $C$ 到 $B$。 今天有 $m$ 位乘客。第 $i$ 位乘客想要从城市 $a_i$ 前往城市 $b_i$。你的任务是，在一天之内，用最少次数的投石机发射，将所有乘客送达目的地，或者判断是否无法完成任务。

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 1000$，$0 \leq m \leq 10^5$），分别表示城市数量和乘客数量。接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$）。

第一行输出一个整数 $k$，表示你需要使用的最少投石机发射次数。 接下来的 $k$ 行，每行输出两个整数 $c_i$ 和 $d_i$，表示一次从城市 $c_i$ 发射到城市 $d_i$ 的投石机发射。 注意，你不需要输出每次发射时应该把哪些乘客放进舱体，但你给出的方案必须能让每位乘客都能到达目的地。 如果无法将所有乘客送达目的地，输出一行 $-1$。

由 ChatGPT 4.1 翻译