#P18703. Are you a bot?
Are you a bot?
Are you a bot?
“如果把机器人的心跳排列成一张图,它会是什么样子?”
你有一个算法竞赛机器人,它的心脏每分钟跳动 次。第 次心跳的强度为 ,其中 是 的一个排列。
设 为从序列 中删除第 个元素得到的序列,即
对于元素两两不同的序列 ,定义无向图 :图中有 个顶点,编号为 。对每一对整数 ,当且仅当对所有整数 都有
在顶点 之间连一条边。
定义 为 中从顶点 到顶点 的最短路径长度,路径长度按边数计算。再定义
给定长度为 的序列 ,请构造任意一个 的排列 ,使得 。保证至少存在一个解。
输入格式
第一行包含一个整数 (),表示测试用例数。
每个测试用例的第一行包含一个整数 ();第二行包含 个整数 。
保证每个测试用例都有解。保证一个输入文件中所有测试用例的 之和不超过 。
输出格式
对每个测试用例输出一行 个整数 ,表示你构造的排列。如果有多个解,输出任意一个。
样例输入
11
4
2 2 1 1
4
2 2 2 2
4
2 1 1 2
7
5 5 4 4 4 5 5
7
1 3 2 2 2 2 4
7
3 3 2 4 4 5 3
8
2 2 3 5 3 3 3 4
8
5 4 4 4 4 6 6 5
8
4 4 4 2 4 4 2 3
9
4 7 5 5 5 5 3 4 4
9
3 4 4 4 4 4 4 4 6
样例输出
1 2 4 3
2 1 4 3
1 3 2 4
3 1 7 2 6 4 5
3 1 6 4 2 5 7
2 3 1 6 4 7 5
5 6 3 1 7 4 2 8
1 8 2 7 3 5 6 4
6 3 2 7 4 5 1 8
5 8 6 3 7 1 9 2 4
8 1 7 9 2 5 3 4 6
样例输出只是各测试用例的一组可行解。