Santa is preparing to deliver his presents this year! The city that he is visiting next is composed of houses numbered from to , and unidirectional edges. Currently, Santa deems the edges to be placed in an inefficient way, so he asks you to arrange them in an efficient way!
Santa considers the city to be efficient if there are exactly neighbourhoods. A group of houses is considered a neighbourhood if for each house you can reach every other house by travelling through some set of edges. In addition, neighbourhoods are as large as possible, there can be no self loops, and every house can only belong to a single neighbourhood.
Just as you deliver your plan, Santa discovers that he can make his trip even more efficient! Santa noticed that he could get his trip done faster if he groups houses that have similar presents in one neighbourhood. So, Santa imposed restrictions on your plan. The -th restriction states that houses and should be in the same neighbourhood.
Help Santa create a valid set of edges that satisfies his restrictions!
Subtask 1 [25%]
Subtask 2 [75%]
No additional constraints.
The first line will contain four space-separated integers, , , , .
The next lines each contain integers and , denoting the -th restriction.
Output lines, each with integers and indicating that a directed path from to is constructed. If there is no possible valid plan, output
If you output an invalid path, repeat a path, or if the plan does not meet the restrictions with neighbourhoods, you will receive
Note: Any valid output will be accepted.
Sample Input 1
5 7 2 1 2 3
Sample Output 1
2 5 3 2 4 3 5 4 2 3 2 4 3 4
Sample Input 2
5 2 3 3 1 2 2 3 3 4
Sample Output 2