#1204. 「HB 省队互测 2019 Round2 Day1」幻相的自平衡

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Edgration

题目描述

slay(Super Logical Algorithm Youth) 是一个风靡全世界的多人对战游戏。

公元 2024 年,巴黎奥运会,中国参赛选手 ViXbob 与日本选手凶真争夺 slay 职业联赛单人竞技冠军。

ViXbob 操纵着喷火器把凶真逼到墙角,切换到红色 RPG,导弹直逼死角...

遥远的地方传来了教练的声音, “ViXbob?”....

这时 ViXbob 从梦中惊醒,发现自己居然在机房里一边看着《命运石之门》,一边打着 slay,打着打着睡着了,被教练抓个正着,之前的一切只是南柯一梦。

但是 ViXbob 还是对梦中的那场 slay 过意不去,她记得梦中的 slay 地图和现在的地图有一些相似之处:两张地图都是一棵 n 个点的树。

不仅如此,ViXbob 还记住了若干个关键点,这些关键点在梦中地图中的度数和在现在地图中的度数相等,除这些点之外不存在在两张地图中度数相同的点

ViXbob 告诉你总点数 n 和她记住的 k 个点,准备问你满足条件的两张地图的方案数。不过她觉得你太菜了肯定不会做这道题,所以只需要你输出任意一组满足条件的两张地图即可。但是 ViXbob 为了刁难你,可能给你的信息根本无解,这个时候请你输出“no solution!”(不带引号)。

输入格式

从标准输入中读入数据。

本题有多组数据。第一行输入一个数字 T ,表示数据组数。

对于每组数据,第一行输入两个数字 n k 。第二行 k 个数,表示在集合中的点的编号。

输出格式

输出到标准输出中。

对于每组数据,如果无解输出输出一行,“no solution!”(不带引号)。

如果有解,输出两行,每行 2n-2 个数字,第一行表示梦中的地图,第二行表示现在的地图,对于 i\in [1,2n-2] ,第 2i-1 个数字和第 2i 个数字表示第 2i−1 个输出和第 2i 个输出之间有一条边。

每组数据之间不需要空一行。

样例

样例输入

3 
5 3 
2 4 5 
5 2
2 4
5 4
1 2 3 4

样例输出

2 1 1 3 1 4 3 5
2 1 1 3 3 4 3 5
1 3 2 1 3 5 4 1
4 5 1 5 3 5 2 5
no solution!

样例解释

对于第一组数据,每个点在第一张图中的度数为 \{3,1,2,1,1\} ,第二张图中的度数为 \{2,1,3,1,1\} 。在两张图中度数相同的点集为 \{2,4,5\} 。当然,只需要输出任意一组满足条件的解即可,不需要和样例输出相同。

数据范围与提示

所有数据满足以下条件。

1\le T\le 10,2\le n\le 10^5,0\le k\le n

子任务

  • 子任务一 (5\%)\ 2\le n\le 3,k=n
  • 子任务二 (10\%)\ 2\le n\le 6
  • 子任务三 (17\%)\ 2\le n\le 15
  • 子任务四 (13\%)\ 2\le n\le 2000
  • 子任务五 (10\%)\ 2\le n\le 10^5,k=0
  • 子任务六 (45\%) 无特殊限制