| Codeforces Round 997 (Div. 2) |
|---|
| Закончено |
Вам дан неориентированный граф с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$. Этот граф кодирует секретную перестановку$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$. Граф строится следующим образом:
- Для каждой пары целых чисел $$$1 \le i < j \le n$$$, между вершиной $$$p_i$$$ и вершиной $$$p_j$$$ добавляется неориентированное ребро тогда и только тогда, когда $$$p_i < p_j$$$. Обратите внимание, что ребро добавляется не между вершинами $$$i$$$ и $$$j$$$, а между вершинами соответствующих им элементов. Обратитесь к примечаниям для лучшего понимания.
Ваша задача состоит в том, чтобы восстановить и вывести перестановку $$$p$$$. Можно доказать, что перестановка $$$p$$$ может быть определена однозначно.
$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 1000$$$).
В $$$i$$$-й из следующих $$$n$$$ строк содержится $$$n$$$ символов $$$g_{i, 1}g_{i, 2}\ldots g_{i, n}$$$ ($$$g_{i, j} = \mathtt{0}$$$ или $$$g_{i, j} = \mathtt{1}$$$) — матрица смежности. $$$g_{i, j} = \mathtt{1}$$$ тогда и только тогда, когда существует ребро между вершинами $$$i$$$ и $$$j$$$.
Гарантируется, что существует перестановка $$$p$$$, которая генерирует данный граф. Также гарантируется, что граф неориентирован и не имеет петель, то есть выполняется $$$g_{i, j} = g_{j, i}$$$ и $$$g_{i, i} = \mathtt{0}$$$.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$1000$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ — восстановленную перестановку.
310500101001011100100001111106000000000000000000000000000000000000
1 4 2 1 3 5 6 5 4 3 2 1
В первом наборе входных данных $$$p = [1]$$$. Поскольку нет пар $$$1 \le i < j \le n$$$, в графе нет рёбер.
Граф для второго набора входных данных показан ниже. Например, когда мы выбираем $$$i = 3$$$ и $$$j = 4$$$, мы добавляем ребро между вершинами $$$p_i = 1$$$ и $$$p_j = 3$$$, потому что $$$p_i < p_j$$$. Однако, когда мы выбираем $$$i = 2$$$ и $$$j = 3$$$, то $$$p_i = 2$$$ и $$$p_j = 1$$$, так что $$$p_i < p_j$$$ не выполняется. Поэтому мы не добавляем ребро между $$$2$$$ и $$$1$$$.
В третьем наборе входных данных в графе нет рёбер, поэтому нет пар целых чисел $$$1 \le i < j \le n$$$ таких, что $$$p_i < p_j$$$. Следовательно, $$$p = [6, 5, 4, 3, 2, 1]$$$.
