Nils is playing a shell swapping game! The game involves ~N~ identical-looking opaque shells being placed in a row, aligned with ~N~ positions labelled from ~1~ to ~N~ from left to right. Initially, the stone is placed under the shell in the ~A~-th position. Then, a man will quickly perform ~M~ swaps; in the ~i~-th swap, the man will choose two different positions ~u_i~ and ~v_i~ and swaps the shells in those positions. If the stone is under a shell being swapped, then the stone will move with that shell, changing position. After the ~M~ swaps, Nils is asked to identify which shell is covering the stone.

With the moves being so fast, Nils is not sure, and guesses that the stone has ended up under the shell in the ~B~-th position. To everyone's surprise, Nils is correct! However, the man is a scammer and is not eager to part with his money - Nils will only receive his reward if he can list all ~M~ swaps that were made!

Unfortunately, the man moved too fast for Nils to see all the moves that were made. Can you help Nils find any sequence of moves that could have resulted in the stone ending up in the ~B~-th position, without contradicting the moves that Nils observed?

Constraints

~3 \le N \le 10^9~

~1 \le M \le 10^6~

~1 \le A, B, u_i, v_i \le N~

~u_i \ne v_i~

There is at least one swap in which Nils did not see which shells were swapped.

It is guaranteed that there exists at least one valid sequence of swaps which matches Nils' observations.

Subtask 1 [30%]

~N = 3~

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains four space-separated integers, ~N, M, A, B~, representing the number of shells, the number of swaps, the starting position of the shell, and the ending position of the shell respectively.

The ~i~-th of the following ~M~ lines represents the ~i~-th swap. If the line contains a single integer ~-1~, then Nils does not know which shells were swapped. Otherwise, the line contains two space-separated integers ~u_i, v_i~, representing the positions of the shells swapped.

Output Specification

Output ~M~ lines. The ~i~-th line should contain two different space-separated integers, representing the positions of the shells swapped. The order of the two integers on any line does not matter. If there are multiple possible sequences of swaps, output any of them.

Sample Input

3 3 1 3
1 2
-1
3 2

Sample Output

1 2
1 3
2 3

Explanation

Nils knows that shells in positions ~1~ and ~2~ were swapped in the first swap, and that the shells in positions ~3~ and ~2~ were swapped in the third swap. However, he did not see which shells were swapped in the second swap.

Consider the scenario where the shells in positions ~1~ and ~3~ were swapped in the second swap. Then, the stone would start at position ~1~, move to position ~2~ after the first swap, stay in position ~2~ after the second swap, and move to position ~3~ after the third swap. This matches Nils' observations, so this output would be accepted.