← 返回题目列表

Codeforces · 1912/H

H. 超级弹射器通勤

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

一个革命性的新型交通系统目前正在 Byteland 运行。该系统既不需要道路,也不需要复杂的机械装置,只需要巨型弹射器。

系统的工作原理如下。 Byteland 有 $$$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$$$。

示例

输入
复制

5 6
1 3
1 2
2 3
4 2
1 5
5 1

输出
复制

5
5 1
1 2
4 2
2 3
3 5

输入
复制

3 6
1 2
1 3
2 1
2 3
3 1
3 2

输出
复制

-1