← 返回题目列表

AtCoder · xmascon23_d

D. 远程施工

中文机器翻译题面 查看原题

配点 : 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