310947: CF1912H. Hypercatapult Commute

H. Hypercatapult Commutetime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

A revolutionary new transport system is currently operating in Byteland. This system requires neither roads nor sophisticated mechanisms, only giant catapults.

The system works as follows. There are $n$ cities in Byteland. In every city there is a catapult, right in the city center. People who want to travel are put in a special capsule, and a catapult throws this capsule to the center of some other city. Every catapult is powerful enough to throw the capsule to any other city, with any number of passengers inside the capsule. The only problem is that it takes a long time to charge the catapult, so it is only possible to use it once a day.

The passenger may need to use the catapults multiple times. For example, if the passenger wants to travel from city A to city B, they can first use one catapult to move from A to C, and then transfer to another catapult to move from C to B.

Today there are $m$ passengers. Passenger $i$ wants to travel from city $a_i$ to city $b_i$. Your task is to find the way to deliver all the passengers to their destinations in a single day, using the minimal possible number of catapults, or say that it is impossible.

Input

The first line of the input contains two integers $n$ and $m$ ($1 \leq n \leq 1000$, $0 \leq m \leq 10^5$) — the number of cities and the number of passengers. The next $m$ lines contain pairs of numbers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$).

Output

In the first line print the number $k$ — the minimal number of catapults you need to use.

In the next $k$ lines, print descriptions of each catapult launch, in the order they need to be performed. Each description should consist of two integers $c_i$, $d_i$, the index of the city to launch from, and the index of destination city.

Note that you don't need to print what passengers should be put into the capsule on each launch, but it should be possible for each passenger to reach their destination city using the plan you provide.

If it is impossible to deliver all passengers, print the single number $-1$.

ExamplesInput

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

Output

5
5 1
1 2
4 2
2 3
3 5

Input

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

Output

-1

题目大意：
Byteland有一个革命性的新交通系统，这个系统不需要道路也不需要复杂的机械，只需要巨型弹射器。系统中有n个城市，每个城市中心都有一个弹射器。人们想要旅行时会被放入一个特殊的胶囊，然后弹射器将这个胶囊发射到另一个城市的中心。每个弹射器都有足够的能量将胶囊发射到任何其他城市，胶囊内可以有任意数量的乘客。唯一的问题是给弹射器充电需要很长时间，所以它每天只能使用一次。

乘客可能需要多次使用弹射器。例如，如果乘客想从A城市到B城市，他们可以先使用一个弹射器从A移动到C，然后转乘另一个弹射器从C移动到B。

今天有m个乘客。第i个乘客想从城市a_i旅行到城市b_i。任务是找到一种方式，在一天内使用最少的弹射器将所有乘客送达他们的目的地，或者判断这是不可能的。

输入输出数据格式：
输入：
第一行包含两个整数n和m（1≤n≤1000，0≤m≤10^5）——城市的数量和乘客的数量。接下来的m行包含数对a_i和b_i（1≤a_i,b_i≤n，a_i≠b_i）。

输出：
第一行打印数字k——你需要的最少弹射器数量。

接下来的k行，按顺序打印每次弹射器发射的描述。每个描述应该由两个整数c_i，d_i组成，分别是从哪个城市的弹射器发射和目的城市。

注意，你不需要打印每次发射应该将哪些乘客放入胶囊中，但必须有可能让每个乘客使用你提供的计划到达他们的目的地城市。

如果无法将所有乘客送达，打印单个数字-1。题目大意： Byteland有一个革命性的新交通系统，这个系统不需要道路也不需要复杂的机械，只需要巨型弹射器。系统中有n个城市，每个城市中心都有一个弹射器。人们想要旅行时会被放入一个特殊的胶囊，然后弹射器将这个胶囊发射到另一个城市的中心。每个弹射器都有足够的能量将胶囊发射到任何其他城市，胶囊内可以有任意数量的乘客。唯一的问题是给弹射器充电需要很长时间，所以它每天只能使用一次。 乘客可能需要多次使用弹射器。例如，如果乘客想从A城市到B城市，他们可以先使用一个弹射器从A移动到C，然后转乘另一个弹射器从C移动到B。 今天有m个乘客。第i个乘客想从城市a_i旅行到城市b_i。任务是找到一种方式，在一天内使用最少的弹射器将所有乘客送达他们的目的地，或者判断这是不可能的。 输入输出数据格式： 输入： 第一行包含两个整数n和m（1≤n≤1000，0≤m≤10^5）——城市的数量和乘客的数量。接下来的m行包含数对a_i和b_i（1≤a_i,b_i≤n，a_i≠b_i）。 输出： 第一行打印数字k——你需要的最少弹射器数量。 接下来的k行，按顺序打印每次弹射器发射的描述。每个描述应该由两个整数c_i，d_i组成，分别是从哪个城市的弹射器发射和目的城市。 注意，你不需要打印每次发射应该将哪些乘客放入胶囊中，但必须有可能让每个乘客使用你提供的计划到达他们的目的地城市。 如果无法将所有乘客送达，打印单个数字-1。