C. Бесплатный сыр
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В итальянской деревне голодная мышь находится в вершине $$$\textrm{st}$$$ заданного дерева$$$^{\text{∗}}$$$ с $$$n$$$ вершинами.

Дана перестановка $$$p$$$ длины $$$n$$$$$$^{\text{†}}$$$, и мышь совершает $$$n$$$ шагов. На $$$i$$$-м шаге:

  • Соблазнительный кусочек пармезана появляется на вершине $$$p_i$$$. Если мышь в данный момент находится на вершине $$$p_i$$$, она останется там и насладится моментом. В противном случае она перейдёт по первому ребру из простого пути до вершины $$$p_i$$$.

Ваша задача — найти такую перестановку, чтобы после всех $$$n$$$ шагов мышь неизбежно оказалась на вершине $$$\textrm{en}$$$, где её поджидает ловушка.

Обратите внимание, что мышь должна оказаться в $$$\textrm{en}$$$ после всех $$$n$$$ шагов, при этом она может проходить через $$$\textrm{en}$$$ ранее в процессе.

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов.

$$$^{\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 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$\textrm{st}$$$ и $$$\textrm{en}$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le \textrm{st}, \textrm{en} \le n$$$) — количество вершин дерева, начальная вершина и вершина с ловушкой.

Каждая из следующих $$$n - 1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — индексы вершин, соединённых ребром.

Гарантируется, что заданные рёбра образуют дерево.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных:

  • Если искомая перестановка не существует, выведите $$$-1$$$.
  • В противном случае выведите $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$, представляющих порядок, в котором сыр будет появляться на вершинах, в результате чего мышь в конце будет поймана на вершине $$$\textrm{en}$$$.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
4
1 1 1
2 1 2
1 2
3 2 2
1 2
2 3
6 1 4
1 2
1 3
4 5
5 6
1 4
Выходные данные
1 
1 2 
3 1 2 
1 4 3 2 6 5
Примечание

В первом наборе входных данных существует только одна перестановка длины $$$n = 1$$$: $$$p = [1]$$$, которая успешно ловит мышь:

$$$$$$\textrm{st} = 1 \overset{p_1 = 1}{\xrightarrow{\hspace{1.3cm}}} 1 = \textrm{en}.$$$$$$

Во втором наборе входных данных одна из возможных перестановок длины $$$n = 2$$$ — это $$$p = [1, 2]$$$:

$$$$$$\textrm{st} = 1 \overset{p_1 = 1}{\xrightarrow{\hspace{1.3cm}}} 1 \overset{p_2 = 2}{\xrightarrow{\hspace{1.3cm}}} 2 = \textrm{en}.$$$$$$

В третьем наборе входных данных одна из возможных перестановок длины $$$n = 3$$$ — это $$$p = [3, 1, 2]$$$:

$$$$$$\textrm{st} = 2 \overset{p_1 = 3}{\xrightarrow{\hspace{1.3cm}}} 3 \overset{p_2 = 1}{\xrightarrow{\hspace{1.3cm}}} 2 \overset{p_3 = 2}{\xrightarrow{\hspace{1.3cm}}} 2 = \textrm{en}.$$$$$$