#P1912H. Hypercatapult Commute
-
ID: 10244
Type: RemoteJudge
3000ms
1024MiB
Tried: 0
Accepted: 0
Difficulty: 9
Uploaded By:
Hydro
Tags> Hypercatapult Commute
Description
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 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 passengers. Passenger wants to travel from city to city . 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.
The first line of the input contains two integers and (, ) — the number of cities and the number of passengers. The next lines contain pairs of numbers and (, ).
In the first line print the number — the minimal number of catapults you need to use.
In the next lines, print descriptions of each catapult launch, in the order they need to be performed. Each description should consist of two integers , , 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 .
Input
The first line of the input contains two integers and (, ) — the number of cities and the number of passengers. The next lines contain pairs of numbers and (, ).
Output
In the first line print the number — the minimal number of catapults you need to use.
In the next lines, print descriptions of each catapult launch, in the order they need to be performed. Each description should consist of two integers , , 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 .