CF1899F.Alex's whims

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Tree is a connected graph without cycles. It can be shown that any tree of nn vertices has exactly n1n - 1 edges.

Leaf is a vertex in the tree with exactly one edge connected to it.

Distance between two vertices uu and vv in a tree is the minimum number of edges that must be passed to come from vertex uu to vertex vv .

Alex's birthday is coming up, and Timofey would like to gift him a tree of nn vertices. However, Alex is a very moody boy. Every day for qq days, he will choose an integer, denoted by the integer chosen on the ii -th day by did_i . If on the ii -th day there are not two leaves in the tree at a distance exactly did_i , 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 uu , v1v_1 , and v2v_2 such that there is an edge between uu and v1v_1 and no edge between uu and v2v_2 . Then remove the edge between uu and v1v_1 and add an edge between uu and v2v_2 . This operation cannot be performed if the graph is no longer a tree after it.

Somehow Timofey managed to find out all the did_i . 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 nn , 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: uu66 , v1v_111 , v2v_244 .

输入格式

The first line contains the integer tt ( 1t1001 \leq t \leq 100 ) — the number of test cases.

The first line of each test case contains two integers nn ( 3n5003 \leq n \leq 500 ) and qq ( 1q5001 \leq q \leq 500 ) — the number of nodes in the tree and the number of days, respectively.

The ii th of the following qq lines contains the integer did_i ( 2din12 \leq d_i \leq n - 1 ).

It is guaranteed that the sum of nn over all test cases does not exceed 500500 . The same is guaranteed for qq .

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 n1n - 1 string describing the edges of the tree. If you want the tree to have an edge between nodes uu and vv , there must be a string vv uu or uu vv among these n1n - 1 lines.

In the next qq lines, print three integers each uu v1v_1 v2v_2 — a description of the operations. If Alex doesn't need to perform an operation the following day, print 1-1 1-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
首页