luogu#P9890. [ICPC2018 Qingdao R] Tournament
[ICPC2018 Qingdao R] Tournament
题目描述
DreamGrid, the king of Gridland, is making a knight tournament. There are knights, numbered from 1 to , participating in the tournament. The rules of the tournament are listed as follows:
- The tournament consists of rounds. Each round consists of several duels. Each duel happens between exactly two knights.
- Each knight must participate in exactly one duel during each round.
- For each pair of knights, there can be at most one duel between them during all the rounds.
- Let , , and , be four distinct integers. If
- Knight fights against knight during round , and
- Knight fights against knight during round , and
- Knight fights against knight during round ,
- then knight must fight against knight during round .
As DreamGrid's general, you are asked to write a program to arrange all the duels in all the rounds, so that the resulting arrangement satisfies the rules above.
输入格式
There are multiple test cases. The first line of the input is an integer , indicating the number of test cases. For each test case:
The first and only line contains two integers and (), indicating the number of knights participating in the tournament and the number of rounds.
It's guaranteed that neither the sum of nor the sum of in all test cases will exceed .
输出格式
For each test case:
- If it's possible to make a valid arrangement, output lines. On the -th line, output integers separated by one space, indicating that in the -th round, knight will fight against knight for all .
If there are multiple valid answers, output the lexicographically smallest answer.
Consider two answers and , let's denote as the -th integer on the -th line in answer , and as the -th integer on the -th line in answer . Answer is lexicographically smaller than answer , if there exists two integers () and (), such that- for all and , , and
- for all , , and finally .
-If it's impossible to make a valid arrangement, output
Impossible
(without quotes) in one line.
Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!
题目大意
个骑士要进行 轮对决,每一轮每个骑士都要有一个对手。而且每个对手只能打一次。假设 与 打了, 与 打了,那么后面的任意一轮如果 与 打了,那么 就必须和 打,问是否存在方案,存在就输出字典序最小的一组,否则输出 Impossible
。
2
3 1
4 3
Impossible
2 1 4 3
3 4 1 2
4 3 2 1