Matching Chameleons at JOI Zoo

At JOI Zoo, there are \(2\times N\) chameleons: \(N\) of gender \(X\) and \(N\) of gender \(Y\). Each chameleon has an original color with the following properties:

• All chameleons of gender \(X\) have distinct original colors.
• For every chameleon of gender \(X\), there exists exactly one chameleon of gender \(Y\) sharing the same original color.

Furthermore, each chameleon loves a chameleon of the opposite gender with these conditions:

• A chameleon only loves a chameleon of the opposite gender.
• The original color of a chameleon is different from the original color of the one it loves.
• No two chameleons love the same chameleon.

You can organize meetings by selecting a subset of chameleons. In a meeting, for every participating chameleon \(s\), let \(t\) be the chameleon that \(s\) loves. Then:

• If \(t\) also participates in the meeting, then \(s\)'s skin color becomes \(t\)'s original color.
• If \(t\) does not participate, then \(s\)'s skin color remains its original color.

After any meeting, you can count the number of distinct skin colors among the participants.

Your task is to determine the pairing of chameleons having the same original color. In other words, determine the \(N\) pairs (each pair consists of one \(X\) and one \(Y\) chameleon with the same original color) by organizing no more than \(2\times10^4\) meetings.

Interaction Details

You must declare two functions:

• int Query(const std::vector<int> &p): This function organizes a meeting with the chameleons whose indices are given in \(p\) (each index is between 1 and \(2\times N\), and all indices in \(p\) must be distinct). It returns the number of distinct skin colors among the participating chameleons. (Violating any condition will result in a wrong answer. You may call this function at most \(2\times10^4\) times.)
• void Answer(int a, int b): This function is used to submit a pair of chameleons (with indices \(a\) and \(b\)) that have the same original color. Each chameleon must appear in exactly one submitted pair and you must call Answer exactly \(N\) times. If the submitted pair does not have the same original color or violates any condition, a wrong answer is returned.

You need to implement a function Solve(int N) which is called once per test case. Your solution may call Query at most \(2\times10^4\) times.

inputFormat

The input consists of a single integer \(N\), indicating that there are \(2\times N\) chameleons.

outputFormat

Output \(N\) lines. Each line should contain two integers \(a\) and \(b\), indicating that chameleon \(a\) and chameleon \(b\) share the same original color.

sample

1

1 2