На большой перемене все n студентов Берляндского государственного университета выстроились в очередь в столовой. Однако оказалось, что у столовой тоже есть перерыв на обед, и она временно перестала работать.
Стоять в очереди, пока она не обслуживается, так скучно! Поэтому каждый из студентов записал номер студенческого билета того студента, что стоит в очереди перед ним, и того, что стоит в очереди непосредственно за ним. Если перед или после студента никого нет (то есть он первый или последний в очереди), то в качестве номера он записал число 0 (билеты студентов Берляндского государственного университета нумеруются с 1).
После этого все студенты разошлись по своим делам. Когда же они вернулись, то оказалось, что восстановить очередь не такая простая задача, как кажется на первый взгляд.
Помогите студентам восстановить состояние очереди по номерам студенческих билетов соседей в очереди.
В первой строке записано целое число n (2 ≤ n ≤ 2·105) — количество студентов в очереди.
Далее следует n строк, где i-я строка содержит пару целых чисел ai, bi (0 ≤ ai, bi ≤ 106), где ai — номер студенческого билета того, кто стоит перед очередным студентом, а bi — номер студенческого билета того, кто стоит после очередного студента. Строки заданы в произвольном порядке. В качестве номера студенческого билета используется значение 0, если такого соседа нет.
У всех студентов номера студенческих билетов различны. Гарантируется, что записи соответствуют очереди, в которой стоят все студенты в каком-то порядке.
Выведите последовательность n целых чисел x1, x2, ..., xn — последовательность номеров студенческих билетов всех студентов в порядке очереди от первого к последнему.
4
92 31
0 7
31 0
7 141
92 7 31 141
Картинка иллюстрирует очередь для первого примера.
| Codeforces Round 279 (Div. 2) |
|---|
| Закончено |
