D - Distance Construction Editorial /

Time Limit: 2 sec / Memory Limit: 2048 MB

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