618B.md (1700B)
1 Source: https://codeforces.com/problemset/problem/618/B 2 3 B. Guess the Permutation 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 Bob has a permutation of integers from 1 to *n*. Denote this permutation as *p*. The *i*-th element of *p* will be denoted as *p**i*. For all pairs of distinct integers *i*, *j* between 1 and *n*, he wrote the number *a**i*, *j* = *min*(*p**i*, *p**j*). He writes *a**i*, *i* = 0 for all integer *i* from 1 to *n*. 22 23 Bob gave you all the values of *a**i*, *j* that he wrote down. Your job is to reconstruct any permutation that could have generated these values. The input will be formed so that it is guaranteed that there is at least one solution that is consistent with the information given. 24 25 Input 26 27 The first line of the input will contain a single integer *n* (2 ≤ *n* ≤ 50). 28 29 The next *n* lines will contain the values of *a**i*, *j*. The *j*-th number on the *i*-th line will represent *a**i*, *j*. The *i*-th number on the *i*-th line will be 0. It's guaranteed that *a**i*, *j* = *a**j*, *i* and there is at least one solution consistent with the information given. 30 31 Output 32 33 Print *n* space separated integers, which represents a permutation that could have generated these values. If there are multiple possible solutions, print any of them. 34 35 Examples 36 37 Input 38 39 ``` 40 2 41 0 1 42 1 0 43 ``` 44 45 Output 46 47 ``` 48 2 1 49 ``` 50 51 Input 52 53 ``` 54 5 55 0 2 2 1 2 56 2 0 4 1 3 57 2 4 0 1 3 58 1 1 1 0 1 59 2 3 3 1 0 60 ``` 61 62 Output 63 64 ``` 65 2 5 4 1 3 66 ``` 67 68 Note 69 70 In the first case, the answer can be {1, 2} or {2, 1}. 71 72 In the second case, another possible answer is {2, 4, 5, 1, 3}.