На натпревар по информатика биле поставени 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.