{"problem":{"name":"Halftree","description":{"content":"We have an undirected graph with $N$ vertices numbered $0$ through $N-1$ and no edges at first. You may add edges to this graph as you like. When you are done with adding edges, the following operatio","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc152_d"},"statements":[{"statement_type":"Markdown","content":"We have an undirected graph with $N$ vertices numbered $0$ through $N-1$ and no edges at first. You may add edges to this graph as you like. When you are done with adding edges, the following operation will be performed once using a given integer $K$.\n\n*   For each edge you have added, let $u$ and $v$ be its endpoints, and an edge will be added between two vertices $(u+K)$ $\\mathrm{mod}$ $N$ and $(v+K)$ $\\mathrm{mod}$ $N$. This edge will be added even if there is already an edge between these vertices, resulting in multi-edges.\n\nFor the given $N$ and $K$, find a set of edges that you should add so that the graph will be a tree after the operation. If there is no such set of edges, indicate that fact.\n\n## Constraints\n\n*   $2\\leq N\\leq 2\\times 10^5$\n*   $1\\leq K\\leq N-1$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc152_d","tags":[],"sample_group":[["5 2","2\n2 3\n2 4\n\nThe operation will add the edges $4$\\-$0$ and $4$\\-$1$. Then, the graph will be a tree, so this is a legitimate output."],["2 1","\\-1\n\nThere is no way to have a tree after the operation."],["7 1","3\n0 1\n2 3\n4 5"]],"created_at":"2026-03-03 11:01:13"}}