$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$를 구하여 출력해 보자.
输入格式
第一行包含一个整数 $k$。($2 \le k \le 12$)
输出格式
第一行输出图 $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$。
样例
输入 1
3
输出 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
说明
下面是 $k=3$ 时一个正确解答的例子。
如上图所示，该图由两棵不重叠的树组成，可以在下图中确认。
计算森林分数得到 $3$，如下所示。红色边属于 $F_1$，蓝色边属于 $F_2$，绿色边属于 $F_3$。
