2060B.md (2960B)
1 Source: https://codeforces.com/problemset/problem/2060/B 2 3 B. Farmer John's Card Game 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Farmer John's $n$ cows are playing a card game! Farmer John has a deck of $n \cdot m$ cards numbered from $0$ to $n \cdot m-1$. He distributes $m$ cards to each of his $n$ cows. 22 23 Farmer John wants the game to be fair, so each cow should only be able to play $1$ card per round. He decides to determine a turn order, determined by a permutation$^{\text{∗}}$ $p$ of length $n$, such that the $p_i$'th cow will be the $i$'th cow to place a card on top of the center pile in a round. 24 25 In other words, the following events happen in order in each round: 26 27 * The $p_1$'th cow places any card from their deck on top of the center pile. 28 * The $p_2$'th cow places any card from their deck on top of the center pile. 29 * ... 30 * The $p_n$'th cow places any card from their deck on top of the center pile. 31 32 There is a catch. Initially, the center pile contains a card numbered $-1$. In order to place a card, the number of the card must be greater than the number of the card on top of the center pile. Then, the newly placed card becomes the top card of the center pile. If a cow cannot place any card in their deck, the game is considered to be lost. 33 34 Farmer John wonders: does there exist $p$ such that it is possible for all of his cows to empty their deck after playing all $m$ rounds of the game? If so, output any valid $p$. Otherwise, output $-1$. 35 36 $^{\text{∗}}$A permutation of length $n$ contains each integer from $1$ to $n$ exactly once 37 38 Input 39 40 The first line contains an integer $t$ ($1 \leq t \leq 400$) — the number of test cases. 41 42 The first line of each test case contains two integers $n$ and $m$ ($1 \leq n \cdot m \leq 2\,000$) — the number of cows and the number of cards each cow receives. 43 44 The following $n$ lines contain $m$ integers each – the cards received by each cow. It is guaranteed all given numbers (across all $n$ lines) are distinct and in the range from $0$ to $n \cdot m - 1$, inclusive. 45 46 It is guaranteed the sum of $n \cdot m$ over all test cases does not exceed $2\,000$. 47 48 Output 49 50 For each test case, output the following on a new line: 51 52 * If $p$ exists, output $n$ space-separated integers $p_1, p_2, \ldots, p_n$. 53 * Otherwise, output $-1$. 54 55 Example 56 57 Input 58 59 ``` 60 4 61 62 2 3 63 64 0 4 2 65 66 1 5 3 67 68 1 1 69 70 0 71 72 2 2 73 74 1 2 75 76 0 3 77 78 4 1 79 80 1 81 82 2 83 84 0 85 86 3 87 ``` 88 89 Output 90 91 ``` 92 1 2 93 1 94 -1 95 3 1 2 4 96 ``` 97 98 Note 99 100 In the first test case, one turn order that allows all cards to be played is by having the first cow go before the second cow. The cards played will be $0\rightarrow1\rightarrow2\rightarrow3\rightarrow4\rightarrow5$. 101 102 In the second test case, there is only one cow, so having the cow play all of her cards in increasing order will empty the deck. 103 104 In the third test case, it can be shown there is no valid turn order that allows all cards to be played.