配点 : 100 点
这个问题本身的存在,Codeforces Round 884 的某个有趣的问题可能会成为什么样的剧透。非常抱歉。
問題文
正整数 M 被给出。判断是否存在满足以下条件的边带权无向树,如果存在, 1 创建一个。
- 頂点数 n 是 您也可以写 2 \le n \le 10^3 很满意。
- 顶点集是 \{1, 2, \ldots, n\} 。
- 每条边的权重是 1 以上 M 小于的整数。
- 各 u = 1, 2, \ldots, n-1 对于,顶点 u 与边缘 u+1 的距离(包括它们之间唯一简单路径的边权之和) M 的倍数。
制約
- 2 \le M \le 10^9.
部分点
- M \le 10^2 的数据集,32 点。 如果所有满足
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 输出(小于 68 点。 如果所有满足
入力
输入是按以下格式从标准输入给出的。
M
出力
如果存在满足条件的边带权无向树,则在这样的树中 1 以以下格式输出它们中的一个:
n
a_1 b_1 c_1
a_2 b_2 c_2
\vdots
a_{n-1} b_{n-1} c_{n-1}
n 是顶点数 (2 \le n \le 10^3).i 番目 (1 \le i \le n-1) 边是顶点 连接 a_i 与边缘 b_i 连接 (1 \le a_i, b_i \le n),权重是 c_i (1 \le c_i < M).
如果不存在满足条件的带权无向树,则改为 -1 。
入力例 1
2
出力例 1
-1