#arc152d. [arc152_d]Halftree

[arc152_d]Halftree

nn 个点 0,1,2...n10,1,2 ... n-1 和一个参数 kk,你需要连接若干条无向边, 使得将这些点连成一棵,连边规则如下:

  • 选择 u,vu,v 两点,同时连接点 uuvv,点 (u+k)modn(u+k)\mod n (v+k)modn(v+k)\mod n

注意可能存在重边,这时重边算作多条边。

求一个合法的构造方案或输出无解。

数据范围:1n2×105,1kn11 \le n \le 2 \times 10^5,1 \le k \le n-1n,kZn,k \in Z