광물

JOI 교수님의 연구실에서는 N가지 광물을 연구하고 있다. 각 광물은 2개씩 존재하여 모두 2N개의 광물 조각이 있고, 조각은 1번부터 2N번까지 번호가 매겨져 있다.

어느 날 조교 Bitaro가 2N개의 조각이 담긴 상자를 떨어뜨려서, 어떤 조각과 어떤 조각이 같은 광물인지 알 수 없게 되었다.

연구실에는 조각을 넣으면 흡수하는 파장을 측정해 들어 있는 광물의 종류 수를 세는 기계가 있다. Bitaro는 2N개의 조각에서 같은 광물끼리 짝지어진 N쌍을 알아내려고 한다. 처음에 기계에는 어떤 조각도 들어 있지 않다. Bitaro는 다음 두 가지 연산을 할 수 있다.

• 조각 하나를 기계에 넣으면, 기계에 들어 있는 광물의 종류 수를 알 수 있다.
• 조각 하나를 기계에서 꺼내면, 기계에 들어 있는 광물의 종류 수를 알 수 있다.

Bitaro가 사고를 낸 사실을 JOI 교수님이 눈치채지 못하게 하려면, 이 연산을 총 1 000 000번 이하로 해야 한다.

광물의 가짓수가 주어질 때, 기계를 사용하여 같은 광물끼리 짝지어진 모든 쌍을 알아내는 프로그램을 작성하라.

• 1 ≤ N ≤ 43 000.
• 1 ≤ Xi ≤ 2N (1 ≤ i ≤ N).
• 1 ≤ Yi ≤ 2N (1 ≤ i ≤ N).
• Xi ≠ Xj (1 ≤ i < j ≤ N).
• Yi ≠ Yj (1 ≤ i < j ≤ N).
• Xi ≠ Yj (1 ≤ i ≤ N, 1 ≤ j ≤ N).

Xi와 Yi (1 ≤ i ≤ N)는 Xi번째 조각과 Yi번째 조각이 같은 광물임을 나타낸다.