Santa is preparing to deliver his presents this year! The city that he is visiting next is composed of ~N~ houses numbered from ~1~ to ~N~, and ~M~ unidirectional edges. Currently, Santa deems the ~M~ 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 ~X~ 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 ~Q~ restrictions on your plan. The ~i~-th restriction states that houses ~x_i~ and ~y_i~ should be in the same neighbourhood.

Help Santa create a valid set of ~M~ edges that satisfies his restrictions!

Constraints

~1 \le N \le 5 \times 10^5~

~1 \le M \le 5 \times 10^5~

~1 \le X \le N~

~0 \le Q \le 5 \times 10^5~

~1 \le x_i, y_i \le N~

~x_i \neq y_i~

Subtask 1 [25%]

~Q = 0~

Subtask 2 [75%]

No additional constraints.

Input Specification

The first line will contain four space-separated integers, ~N~, ~M~, ~X~, ~Q~.

The next ~Q~ lines each contain ~2~ integers ~x_i~ and ~y_i~, denoting the ~i~-th restriction.

Output Specification

Output ~M~ lines, each with ~2~ integers ~u~ ~(1 \le u \le N)~ and ~v~ ~(1 \le v \le N)~ indicating that a directed path from ~u~ to ~v~ is constructed. If there is no possible valid plan, output -1.

If you output an invalid path, repeat a path, or if the plan does not meet the ~Q~ restrictions with ~X~ neighbourhoods, you will receive WA.

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

-1