Tree
TopCoder TCO2016, Round 1A
Time Limit: 1.5s, Memory Limit: 128MiB
Ели има граф с N+1 върха, номерирани от 0 до N. Графът всъщност е кореново дърво с корен върхът 0.
Ели може да се движи между върхове в дървото скачайки от един връх в друг. Не всички скокове между върхове са разрешени. Момичето може да скочи от връх A във връх B, само ако единият от тях е директен или индиректен наследник на другия.
В момента Ели се намира във връх 0 (корена на дървото). Тя иска да направи поредица от N скока, така че да посети всеки от останалите върхове на дървото точно по веднъж. Забележете, че момичето може да прескача вече посетени върхове. Например, ако B е наследник на A, а C е наследник на B, то Ели може да скочи от A в C или от C в A, дори ако B вече е посетен.
Ели може да се движи между върхове в дървото скачайки от един връх в друг. Не всички скокове между върхове са разрешени. Момичето може да скочи от връх A във връх B, само ако единият от тях е директен или индиректен наследник на другия.
В момента Ели се намира във връх 0 (корена на дървото). Тя иска да направи поредица от N скока, така че да посети всеки от останалите върхове на дървото точно по веднъж. Забележете, че момичето може да прескача вече посетени върхове. Например, ако B е наследник на A, а C е наследник на B, то Ели може да скочи от A в C или от C в A, дори ако B вече е посетен.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N – броя върхове, които Ели иска да посети. На следващия ред са зададени N на брой цели числа Pi – родителите на, съответно, връх 1, 2, ..., N.
Изход
Ако е възможно Ели да обиколи всичките оставащи върхове точно по веднъж, на един ред на стандартния изход изведете реда, в който момичето трябва да ги обходи. Ако съществува повече от едно решение, изведете лексикографски най-малкото. Ако няма решение, вместо това изведете "IMPOSSIBLE".
Ограничения
- 0 ≤ Pi ≤ N
- 1 ≤ N ≤ 5,000
Примерен Вход | Примерен Изход |
---|---|
15 9 13 7 9 8 14 14 0 6 9 2 2 5 5 7 | 1 5 2 11 13 12 8 3 7 15 14 4 6 9 10 |
2 0 0 | IMPOSSIBLE |
В първия тест, върховете, които Ели може да посети от връх 6, са: {0, 8, 5, 14, 9, 10, 1, 4}.
Във втория тест връх 0 има две деца – връх 1 и връх 2. Което и от тях да избере, след това няма как да стигне до другото.