CF1899F.Alex's whims
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Tree is a connected graph without cycles. It can be shown that any tree of n vertices has exactly n−1 edges.
Leaf is a vertex in the tree with exactly one edge connected to it.
Distance between two vertices u and v in a tree is the minimum number of edges that must be passed to come from vertex u to vertex v .
Alex's birthday is coming up, and Timofey would like to gift him a tree of n vertices. However, Alex is a very moody boy. Every day for q days, he will choose an integer, denoted by the integer chosen on the i -th day by di . If on the i -th day there are not two leaves in the tree at a distance exactly di , Alex will be disappointed.
Timofey decides to gift Alex a designer so that he can change his tree as he wants. Timofey knows that Alex is also lazy (a disaster, not a human being), so at the beginning of every day, he can perform no more than one operation of the following kind:
- Choose vertices u , v1 , and v2 such that there is an edge between u and v1 and no edge between u and v2 . Then remove the edge between u and v1 and add an edge between u and v2 . This operation cannot be performed if the graph is no longer a tree after it.
Somehow Timofey managed to find out all the di . After that, he had another brilliant idea — just in case, make an instruction manual for the set, one that Alex wouldn't be disappointed.
Timofey is not as lazy as Alex, but when he saw the integer n , he quickly lost the desire to develop the instruction and the original tree, so he assigned this task to you. It can be shown that a tree and a sequence of operations satisfying the described conditions always exist.
Here is an example of an operation where vertices were selected: u — 6 , v1 — 1 , v2 — 4 .
输入格式
The first line contains the integer t ( 1≤t≤100 ) — the number of test cases.
The first line of each test case contains two integers n ( 3≤n≤500 ) and q ( 1≤q≤500 ) — the number of nodes in the tree and the number of days, respectively.
The i th of the following q lines contains the integer di ( 2≤di≤n−1 ).
It is guaranteed that the sum of n over all test cases does not exceed 500 . The same is guaranteed for q .
It can be shown that a tree and a sequence of operations satisfying the described conditions always exist.
输出格式
For each test case, first print an n−1 string describing the edges of the tree. If you want the tree to have an edge between nodes u and v , there must be a string v u or u v among these n−1 lines.
In the next q lines, print three integers each u v1 v2 — a description of the operations. If Alex doesn't need to perform an operation the following day, print −1 −1 −1 .
输入输出样例
输入#1
3 3 3 2 2 2 5 6 4 2 3 4 3 2 4 9 2 3 3 2 2 2 3 2 2
输出#1
1 2 2 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 2 2 3 3 4 4 5 -1 -1 -1 4 3 2 5 4 3 4 2 5 4 5 2 5 3 4 1 2 2 3 3 4 4 3 2 4 2 3 -1 -1 -1 4 3 2 -1 -1 -1 -1 -1 -1 4 2 3 4 3 2 -1 -1 -1