用户 ainta 喜欢树。这次他要制作一棵有 n 个顶点的无向树,顶点编号为 1 到 n 的整数。该树是加权的,因此树的每条边都有一些整数权重。
他还有一个数组 t:t[1], t[2], ..., t[n]。首先,数组的所有元素都初始化为 0。然后,对于连接权重为 c 的树的顶点 u 和 v (u < v) 的每条边,ainta 将值 c 添加到数组 t 的元素 t[u]、t[u + 1]、...、t[v - 1]、t[v]。
假设 d(u, v) 是顶点 u 和顶点 v 之间最短路径上的边的总权重。当且仅当 d(x, y) = t[x] + t[x + 1] + ... + t[y - 1] + t[y] 时,用户 ainta 称一对整数 x, y (1 ≤ x < y ≤ n) 为良好。
用户 ainta 想要至少生成 $$\left\lfloor \frac{n}{2} \right\rfloor$$ 好的对,但他无法生成合适的树。帮助安塔找到这样一棵树。
输入
第一行包含一个整数 n (5 ≤ n ≤ 105)。
输出
打印包含边缘描述的 n - 1 行。第 i 行应包含三个以空格分隔的整数 ui、vi、ci (1 ≤ ui < vi ≤ n; 1 ≤ ci ≤ 105) — 由边连接的两个顶点以及边的权重。
接下来打印包含好对的 $$\left\lfloor \frac{n}{2} \right\rfloor$$ 行。第 k 行应包含两个以空格分隔的整数 xk 和 yk (1 ≤ xk < yk ≤ n)。当然,xk、yk一定是一对好搭档。所有对都应该是不同的 - 也就是说,对于所有 j,必须满足 k $$( 1 \leq j < k \leq [ \frac { n } { 2 } ] )$$、xj ≠ xk 或 yj ≠ yk 。
如果有多个正确答案,请打印其中任何一个。
示例
输入 #1
7
输出 #1
1 4 1 1 2 2 2 3 5 3 5 3 2 6 2 6 7 3 4 5 5 6 5 7
注意
⌊x⌋ 是不大于 x 的最大整数。
您可以通过以下链接找到树的定义:http://en.wikipedia.org/wiki/Tree_(graph_theory)
您还可以通过以下链接找到最短路径的定义:http://en.wikipedia.org/wiki/Shortest_path_problem
示例输出中的树和数组 t 如下所示: