$1$번부터 $N$번까지 $N$개 정점과 $M$개 간선으로 이루어진 가중치 있는 무방향 단순 그래프 $G$에 대해 숲 점수를 다음과 같이 정의한다:
- $F_1$, $F_2$, $F_3$, $\ldots$, $F_M$ 각각을 $1$번부터 $N$번까지 $N$개 정점으로 이루어져 있으며 간선이 없는 그래프라 하자.
- $G$의 간선들을 가중치 오름차순으로 $e_1$, $e_2$, $\ldots$, $e_M$이라 할 때, $i=1, 2, \ldots, M$에 대해 순서대로 다음을 시행한다:
- $F_j$에 $e_i$를 추가했을 때 사이클이 생기지 않는 최소의 양의 정수 $j$를 찾아 $F_j$에 $e_i$를 추가한다. 여기서 $e_i$를 추가한다는 것은 $e_i$의 양 끝 정점의 번호가 $u_i$, $v_i$일 때 $F_j$에 $u_i$번 정점과 $v_i$번 정점을 잇는 간선을 추가하는 것을 뜻한다.
- $F_i$가 하나 이상의 간선을 가지는 가장 큰 $i$를 그래프 $G$의 숲 점수라 한다.
당신은 양의 정수 $k$에 대해 숲 점수가 정확히 $k$이고 정점이 $2024$개 이하인 그래프 $G$를 생성하라는 임무를 받았다.
이 문제가 너무 쉬웠던 당신에게는 다음과 같은 추가적인 조건을 만족하는 $G$를 찾는 것이 더 흥미롭게 느껴졌다.
- $G$의 정점의 개수를 $N$이라 하면, 간선의 개수는 $(2N-2)$이다.
- $G$의 간선 중 $(N-1)$개는 빨간색, 다른 $(N-1)$개는 파란색으로 칠해서 빨간색 간선만 남겼을 때 트리가 되고, 파란색 간선만 남겨도 트리가 되도록 할 수 있다.
$k$가 주어질 때, 조건을 만족시키는 $G$를 구하여 출력해 보자.
Input
첫 줄에 정수 $k$가 주어진다. ($2 \le k \le 12$)
Output
첫 줄에 그래프 $G$의 정점의 개수 $N$을 출력한다. ($2 \le N \le 2024$)
둘째 줄부터 $(2N-2)$개의 줄에 걸쳐 $i$번째 줄에 세 정수 $a_i$, $b_i$, $c_i$를 공백을 사이에 두고 출력한다. ($1 \le a_i, b_i \le N$; $a_i \neq b_i$; $1 \le c_i \le 10^9$) 이는 $a_i$번 정점과 $b_i$번 정점을 잇는 가중치 $c_i$인 간선이 존재함을 나타낸다.
$G$는 다음 조건들을 충족해야 한다.
- 모든 간선의 가중치는 서로 다르다. 즉, $c_i$끼리는 서로 다르다.
- 출력한 첫 $N-1$개의 간선은 트리를 이룬다. 마찬가지로, 그 뒤에 출력한 $N-1$개 간선도 트리를 이룬다.
- 두 개 이상의 간선으로 직접 연결된 정점 쌍이 존재하지 않는다.
- $G$의 숲 점수는 $k$이다.
Examples
Input 1
3
Output 1
5 1 2 8 2 3 1 3 4 2 4 5 5 1 3 6 3 5 4 5 2 7 2 4 3
Note
아래는 $k=3$인 경우 올바른 답의 예시이다.
위 그래프는 아래 그림에서 확인할 수 있듯 겹치지 않는 두 개의 트리로 구성된다.
숲 점수를 계산해 보면 아래와 같이 $3$이 된다. 빨간색 간선은 $F_1$, 파란색 간선은 $F_2$, 초록색 간선은 $F_3$에 소속된 간선을 나타낸다.
