← 返回题目列表

Codeforces · 1899/F

F. 亚历克斯的突发奇想

中文机器翻译题面 查看原题

树是一个没有环的连通图。可以证明,任意 $$$n$$$ 个顶点的树都恰好有 $$$n - 1$$$ 条边。

叶子是树中的一个顶点,只有一条边与之相连。

树中两个顶点 $$$u$$$ 和 $$$v$$$ 之间的距离是从顶点 $$$u$$$ 到顶点 $$$v$$$ 必须传递的最小边数。

Alex 的生日即将到来,Timofey 想送他一棵由 $$$n$$$ 顶点组成的树。然而,亚历克斯是一个非常喜怒无常的男孩。在$$$q$$$天里,他每天都会选择一个整数,用$$$d_i$$$在第$$$i$$$天选择的整数来表示。如果在第 $$$i$$$ 天,树上没有两片叶子的距离恰好为 $$$d_i$$$,Alex 会感到失望。

Timofey 决定送给 Alex 一位设计师,以便他可以按照自己的意愿改变他的树。 Timofey 知道 Alex 也很懒(一场灾难,不是一个人),所以每天一开始,他只能执行以下一种操作:

- 选择顶点 $$$u$$$、$$$v_1$$$ 和 $$$v_2$$$,使得 $$$u$$$ 和 $$$v_1$$$ 之间有边,而 $$$u$$$ 和 $$$v_2$$$ 之间没有边。然后删除 $$$u$$$ 和 $$$v_1$$$ 之间的边,并在 $$$u$$$ 和 $$$v_2$$$ 之间添加一条边。如果后面的图不再是树,则无法执行此操作。

Timofey 不知何故设法找出了所有 $$$d_i$$$。之后,他有了另一个绝妙的主意——以防万一,为这套设备制作一本使用手册,亚历克斯不会失望的。

Timofey不像Alex那么懒,但是当他看到整数$$$n$$$时,他很快就失去了开发指令和原始树的欲望,所以他把这个任务分配给了你。可以证明,满足所描述条件的树和操作序列总是存在的。

以下是选择顶点的操作示例:$$$u$$$ — $$$6$$$、$$$v_1$$$ — $$$1$$$、$$$v_2$$$ — $$$4$$$。

输入

第一行包含整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ ($$$3 \leq n \leq 500$$$) 和 $$$q$$$ ($$$1 \leq q \leq 500$$$) - 分别是树中的节点数和天数。

以下 $$$q$$$ 行中的第 $$$i$$$ 行包含整数 $$$d_i$$$ ($$$2 \leq d_i \leq n - 1$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$500$$$。 $$$q$$$ 也能保证同样的效果。

可以证明,满足所描述条件的树和操作序列总是存在的。

输出

对于每个测试用例,首先打印一个描述树边缘的 $$$n - 1$$$ 字符串。如果您希望树在节点 $$$u$$$ 和 $$$v$$$ 之间有一条边,则这些 $$$n - 1$$$ 行中必须有字符串 $$$v$$$ $$$u$$$ 或 $$$u$$$ $$$v$$$ 。

在接下来的 $$$q$$$ 行中,打印三个整数,每个 $$$u$$$ $$$v_1$$$ $$$v_2$$$ - 操作的描述。如果 Alex 第二天不需要执行操作,则打印 $$$-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