P12439 [NERC2023] 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$，分别表示发射城市和目的城市的编号。 注意：你不需要具体说明每次弹射搭载哪些乘客，但需确保根据你提供的方案，所有乘客都能抵达目的地。 若无法完成所有运输任务，则输出单个数字 $-1$。

翻译由 DeepSeek V3 完成