Структура некоторой корпорации такова, что каждый служащий, кроме
служащих нижнего звена, является непосредственным начальником не менее чем
одного другого служащего (возможно, служащего нижнего звена). Во главе компании
стоит Президент, которому подчиняются либо непосредственно, либо по должностной
иерархии все остальные служащие. Каждый служащий (разумеется, кроме Президента)
имеет одного непосредственного начальника. Все служащие в этой структуре имеют
индивидуальные номера от 1 до N (2 £ N £ 1000). Пример описания такой структуры приведён на
рисунке, где сотрудник с номером 3 является Президентом и непосредственным
начальником сотрудников с номерами 1 и 4, а сотрудник с номером 4 является
непосредственным начальником сотрудника с номером 2. Структура корпорации
является корпоративной тайной и строго охраняется.
По итогам года Президент компании, довольный работой всех
служащих нижнего звена, решил направить в адрес каждого из них благодарственное
письмо. Передача писем этим служащим осуществлялась через их непосредственных
начальников с использованием сайта корпорации. В результате этого каждый
служащий нижнего звена получил благодарственное письмо от Президента компании,
но на сайте оказался доступным перечень всех путей следования писем от
Президента до каждого служащего нижнего звена.
Требуется написать программу, которая по сведениям,
доступным на сайте, восстанавливает структуру корпорации.
Формат входных данных:
Во входном файле на одной строке содержится
последовательность чисел, определяющая все пути следования писем от Президента
до каждого служащего нижнего звена. Каждый путь описывается соответствующими
номерами служащих, разделённых пробелами. Например, для приведённой на рисунке
структуры таких путей будет два: 3–4–2 и 3–1. Пути в последовательности
указываются в произвольном порядке. Гарантируется, что заданная
последовательность корректна, то есть существует корпорация, ей
соответствующая.
Формат выходных данных:
Выходной файл должен содержать N
строк. В i-й строке (1 £ i £ N)
должны располагаться в возрастающем порядке номера всех служащих,
непосредственно подчинённых i-му служащему. Все
числа в строке разделены пробелом. Последним в каждой строке должно быть число
0. Если решений несколько, необходимо вывести любое.
Пример файлов входных и выходных данных:
|
INPUT
|
OUTPUT
|
|
3 4 2 3 1
|
0
0
1 4 0
2 0
|
