문자열 문제

Lara는 벼룩시장을 매우 좋아한다. 지난 토요일, 독일에서 가장 큰 벼룩시장 중 하나인 Rheinaue-Flohmarkt가 Bonn에서 열렸다. 물론 Lara는 하루 종일 그곳에서 시장을 돌아다니고, 가격을 흥정하고, 온갖 신기한 물건을 사며 보냈다. 그녀가 집으로 가져온 물건 중 가장 흥미로운 것은 완벽한 원형의 작은 하프였다. 그녀가 하프를 연주하려고 했을 때, 현들이 서로 평행하지 않고 제멋대로 놓여 있다는 것을 알아차렸다.

더 구체적으로 말하면, 원형 틀을 따라 $2\cdot N$개의 핀이 균등하게 배치되어 있다. $N$개의 현은 각각 두 핀에 의해 고정되어 있으며, 모든 핀에는 정확히 하나의 현이 연결되어 있다.

Lara는 하프에 관해 잘 알지는 못하지만, 현들이 서로 평행하도록 정렬되어야 한다고 굳게 생각한다. 이 문제를 해결하기 위해 그녀는 하프의 현을 다시 연결하기로 한다. 각 단계에서 그녀는 현의 한쪽 끝을 핀에서 분리한 뒤 다른 핀에 다시 연결할 수 있다. 이 과정에서는 여러 현의 끝이 같은 핀에 연결되어 있어도 된다. 마지막에는 다시 모든 핀에 정확히 하나의 현이 연결되어 있어야 하며, $N$개의 현은 서로 평행해야 한다.

아래에서 현들이 평행한 하프의 두 가지 예를 볼 수 있다.

현을 다시 연결하는 각 단계에는 많은 노력이 들기 때문에, Lara는 가능한 한 적은 단계로 하프의 현을 다시 연결하고 싶어 한다. Lara가 최소 단계 수로 이루어진 현 재연결 순서를 찾도록 도와주자!

제약 조건 및 채점

• $4 \leq N \leq 100\,000$.

• $0 \leq a_i, b_i \leq 2\cdot N - 1$.

• 모든 $a_i$와 $b_i$는 서로 다르다.

여러 테스트 그룹으로 구성된 테스트로 풀이를 평가하며, 각 그룹에는 일정한 점수가 배정되어 있다. 각 테스트 그룹은 여러 테스트 케이스를 포함한다. 각 테스트 그룹에서 받는 점수는 다음과 같이 결정된다.

• 프로그램이 해당 테스트 그룹의 모든 테스트 케이스를 해결하면 점수의 $100\%$를 받는다.

• 프로그램이 해당 테스트 그룹을 완전히 해결하지는 못했지만 각 테스트 케이스에 대해 최소 단계 수를 올바르게 출력했다면, 점수의 $50\%$를 받는다.

풀이가 테스트 그룹 점수의 $50\%$를 받는지를 결정할 때는 출력한 값 $K$만 채점한다. 풀이가 값 $K$만 출력하고 종료해도 되고, 심지어 올바르지 않은 이동 순서를 출력해도 된다. 단, 풀이가 여전히 제한 시간 내에 실행을 마치고 올바르게 종료해야 한다는 점에 유의하라.

그룹 | 점수 | 제한

1 | 14 | 모든 $i$에 대해 현 $i$이 핀 $2\cdot i$와 $2\cdot i + 1$에 연결되어 있다

2 | 16 | 필요한 단계 수가 최대 $2$이다

3 | 12 | 하나의 현이 핀 $0$와 $1$에 연결되는 해가 존재함이 보장된다

4 | 28 | $N \leq 1\,000$

5 | 30 | 추가 제약 조건 없음

예제

첫 번째 예제에서는 다섯 개의 현이 있는 하프가 주어진다. 첫 번째 단계에서 현 $4$을 핀 $8$에서 분리하여 핀 $9$에 다시 연결한다. 다음 단계에서 현 $0$을 핀 $5$에서 분리하여 핀 $8$에 다시 연결한다. 마지막 단계에서 현 $1$을 핀 $9$에서 분리하여 핀 $5$에 다시 연결한다. 이제 각 핀에 정확히 하나의 현이 연결되어 있고, 모든 현이 서로 평행하다. 이 순서는 아래 그림에 나타나 있다.

아래 그림은 예제 2, 3, 4에서 하프의 초기 상태를 보여 준다.

• 첫 번째 예제는 테스트 그룹 4와 5의 제약 조건을 만족한다.

• 두 번째 예제는 테스트 그룹 1, 3, 4, 5의 제약 조건을 만족한다.

• 세 번째 예제는 테스트 그룹 2, 4, 5의 제약 조건을 만족한다.

• 네 번째 예제는 테스트 그룹 3, 4, 5의 제약 조건을 만족한다.

입력의 첫 번째 줄에는 현의 개수를 나타내는 정수 하나 $N$이 주어진다. 현에는 $0$부터 $N - 1$까지 번호가 매겨져 있다.

이어서 $N$개의 줄이 주어지며, $i$번째 줄에는 ($0\le i \le N-1$) 두 정수 $a_i$와 $b_i$가 주어진다. 이들은 $i$번째 현을 고정하는 두 핀이다. 핀에는 시계 방향으로 $0$부터 $2\cdot N - 1$까지 번호가 매겨져 있다. 모든 핀에는 정확히 하나의 현이 연결되어 있다.

모든 현이 서로 평행하도록 하프의 현을 다시 연결하는 데 필요한 최소 단계 수를 나타내는 정수 $K$을 출력한다.

이어서 $K$개의 줄을 출력한다. 각 줄에는 세 정수 $p$, $s$, $e$를 출력하며, 이는 풀이의 이 단계에서 $p$번째 현의 한쪽 끝을 핀 $s$에서 분리하여 핀 $e$에 다시 연결해야 함을 나타낸다 ($0 \leq p \leq N - 1$, $0 \leq s, e \leq 2\cdot N - 1$).

그 순간 $p$번째 현이 핀 $s$에 연결되어 있지 않다면 이동 순서는 올바르지 않은 것으로 간주된다는 점에 유의하라.

답이 여러 개라면 그중 아무거나 출력해도 된다. 다음 절에서 설명한 것처럼 부분적으로 올바른 답도 일부 점수를 받을 수 있음에 유의하라.