Реконструкција
На натпревар по информатика биле поставени K+1 компјутери во една долга права редица. На нив Бојана, која е одговорна за распоредување на натпреварувачите, требало да ги постави натпреварувачите. Натпреварувачите се означени со броеви од 0 до K, и требало да бидат поставени на компјутерите по ред: 0, 1, 2,..., K. Бојана кога ги поставувала не обрнала внимание, па тие седнале произволно. Кога проверила, видела дека прв е натпреварувачот означен со 0, а последен е натпреварувачот означен со K и за неа тоа било доволно.
Кога поминал, организаторот на натпреварувањето сфатил дека редоследот не е како што треба, па и се навикал на Бојана и ѝ дал задача да запише како тие седат по редослед.
Таа, сеуште нерасонета и изнервирана, наместо да ги запише еден по еден, ги запишала во парови, односно запишала кој натпреварувач до кој седи. Уште повеќе, не ни внимавала кој е од лево, а кој е од десно. Таа успеала да ги запише сите парови од соседи (на пример: првиот и вториот, вториот и третиот, четвртиот и третиот...) освен еден.
Кога завршил натпреварот, таа сфатила дека сега има дополнителна работа точно да ја реконструира низата, но знаејќи кои податоци ги има (дека на почеток е натпреварувачот означен со 0, на крај тој означен со K, како и запишаните K-1 парови), било јасно дека успешно ќе ја заврши работата.
Дали вие ќе можете да ја реконструирате низата со програма, имајќи предвид дека бројот K може да достигне до 100 000?
Влез
Во првиот ред ќе биде зададен бројот K<=100 000. Во секој од следните K–1 редови, се запишани по 2 броја кои го претставуваат еден од паровите кои ги запишала Бојана.
Забелешка: Во тест примери кои носат 70% од поените, K<=1000.
Излез
Во првиот ред од излезот треба да се испишат броевите на натпреварувачите по редослед на седење, започнувајќи со натпреварувачот означен со 0 и завршувајќи со тој означен со K.
Ограничувања
Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes
Примери
влез 7 3 6 4 1 4 7 5 2 6 1 5 0 | излез 0 5 2 3 6 1 4 7 |
влез 4 0 3 1 3 2 4 | излез 0 3 1 2 4 |
Објаснување за вториот тест пример: Во дадените парови соседи недостасува инфомрација за соседите 2 и 1.