Мы загадали перестановку \(p\), состоящую из \(n\) целых чисел. Перестановкой длины \(n\) называется массив длины \(n\), где каждый элемент от \(1\) до \(n\) встречается ровно один раз. Эта перестановка вам неизвестна.
Для каждой позиции \(r\) от \(2\) до \(n\) мы выбрали некоторый другой индекс \(l\) (\(l < r\)) и дали вам отрезок \(p_l, p_{l + 1}, \dots, p_r\) в отсортированном порядке (то есть мы переставили элементы на этом отрезке так, что элементы на этом отрезке оказались отсортированными). Таким образом, вам задан ровно \(n-1\) отрезок первоначальной перестановки, но элементы внутри каждого отрезка отсортированы. Отрезки даны вам в случайном порядке.
Например, если загаданная перестановка — \(p=[3, 1, 4, 6, 2, 5]\), то возможное заданное множество отрезков:
- \([2, 5, 6]\)
- \([4, 6]\)
- \([1, 3, 4]\)
- \([1, 3]\)
- \([1, 2, 4, 6]\)
Ваша задача — найти любую подходящую перестановку (то есть любую перестановку, соответствующую входным данным). Гарантируется, что входные данные соответствуют некоторой перестановке (то есть перестановка существует).
Вам нужно ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ: \(n\) целых чисел \(p_1, p_2, \dots, p_n\) (\(1 \le p_i \le n\), все \(p_i\) должны быть различны) — любую подходящую перестановку (то есть любую перестановку, удовлетворяющую входным данным набора тестовых данных).