Chameleon’s Love

In JOI Zoo, there are 2N chameleons, numbered from 1 to 2N. Among them, N chameleons have sex X. The remaining N chameleons have sex Y.

Each chameleon has its original color. The following are known about the original colors.

• The original colors of the N chameleons of sex X are distinct.
• For each chameleon of sex X, there exists a unique chameleon of sex Y with the same original color.

Now, JOI Zoo is in the season of new loves.

• Each chameleon loves another chameleon. The following are known about the chameleons’ loves. • Each chameleon loves exactly one chameleon whose sex is different from itself.
• A chameleon and the chameleon which it loves have different original colors.
• There do not exist two chameleons which love the same chameleon.

You can gather some of the chameleons and organize a meeting. For each chameleon s attending the meeting, let t be the chameleon which s loves. The skin color of s is decided as follows.

• If t attends the meeting, the skin color of s is the original color of t.
• If t does not attend the meeting, the skin color of s is the original color of s.

The skin color of a chameleon may change for different meetings. For each meeting you organize, you can count the number of kinds of skin colors of the chameleons attending the meeting.

By organizing meetings at most 20 000 times, you want to determine all pairs of chameleons with the same original color.

Write a program which, given the number of chameleons, determines all pairs of chameleons with the same original color by organizing meetings at most 20 000 times.

• 2 ≤ N ≤ 500.
• 0 ≤ Yi ≤ 1 (1 ≤ i ≤ 2N).
• 1 ≤ Ci ≤ N (1 ≤ i ≤ 2N).
• For each j (1 ≤ j ≤ N), there exists a unique i (1 ≤ i ≤ 2N) satisfying Yi = 0 and Ci = j.
• For each j (1 ≤ j ≤ N), there exists a unique i (1 ≤ i ≤ 2N) satisfying Yi = 1 and Ci = j.
• 1 ≤ Li ≤ 2N (1 ≤ i ≤ 2N).
• Yi ≠ YLi (1 ≤ i ≤ 2N).
• Ci ≠ CLi (1 ≤ i ≤ 2N).
• Lk ≠ Ll (1 ≤ k < l ≤ 2N).

Yi (1 ≤ i ≤ 2N) is the sex of the chameleon i, which is 0 or 1. It is 0 if the sex is X, and 1 if the sex is Y.

Ci (1 ≤ i ≤ 2N) is the original color of the chameleon i, which is an integer greater than or equal to 1 and less than or equal to N.

Li (1 ≤ i ≤ 2N) is the number of the chameleon which the chameleon i loves.