luogu#P9890. [ICPC2018 Qingdao R] Tournament

[ICPC2018 Qingdao R] Tournament

题目描述

DreamGrid, the king of Gridland, is making a knight tournament. There are nn knights, numbered from 1 to nn, participating in the tournament. The rules of the tournament are listed as follows:

  • The tournament consists of kk 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 kk rounds.
  • Let 1i,jk1 \le i, j \le k, iji \ne j, and 1a,b,c,dn1 \le a, b, c, d \le n, a,b,c,da, b, c, d be four distinct integers. If
    • Knight aa fights against knight bb during round ii, and
    • Knight cc fights against knight dd during round ii, and
    • Knight aa fights against knight cc during round jj,
  • then knight bb must fight against knight dd during round jj.

As DreamGrid's general, you are asked to write a program to arrange all the duels in all the kk rounds, so that the resulting arrangement satisfies the rules above.

输入格式

There are multiple test cases. The first line of the input is an integer TT, indicating the number of test cases. For each test case:

The first and only line contains two integers nn and kk (1n,k10001 \le n, k \le 1000), indicating the number of knights participating in the tournament and the number of rounds.

It's guaranteed that neither the sum of nn nor the sum of kk in all test cases will exceed 50005000.

输出格式

For each test case:

  • If it's possible to make a valid arrangement, output kk lines. On the ii-th line, output nn integers ci,1,ci,2,,ci,nc_{i, 1}, c_{i, 2}, \dots, c_{i, n} separated by one space, indicating that in the ii-th round, knight jj will fight against knight ci,jc_{i, j} for all 1jn1 \le j \le n.
    If there are multiple valid answers, output the lexicographically smallest answer.
    Consider two answers AA and BB, let's denote ai,ja_{i, j} as the jj-th integer on the ii-th line in answer AA, and bi,jb_{i, j} as the jj-th integer on the ii-th line in answer BB. Answer AA is lexicographically smaller than answer BB, if there exists two integers pp (1pk1 \le p \le k) and qq (1qn1 \le q \le n), such that
    • for all 1i<p1 \le i < p and 1jn1 \le j \le n, ai,j=bi,ja_{i, j} = b_{i, j}, and
    • for all 1j<q1 \le j < q, ap,j=bp,ja_{p, j} = b_{p, j}, and finally ap,q<bp,qa_{p, q} < b_{p, q}. -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!

题目大意

nn 个骑士要进行 mm 轮对决,每一轮每个骑士都要有一个对手。而且每个对手只能打一次。假设 aabb 打了,ccdd 打了,那么后面的任意一轮如果 aacc 打了,那么 bb 就必须和 dd 打,问是否存在方案,存在就输出字典序最小的一组,否则输出 Impossible

2
3 1
4 3
Impossible
2 1 4 3
3 4 1 2
4 3 2 1