Problem
Asya sangat menyayangi haiwan. Dia baru-baru ini membeli n anak kucing, memberi mereka pengecam berangka dari 1 hingga n, dan meletakkannya di dalam kandang. Burung burung ialah deretan n sel, juga bernombor dari 1 hingga n. Sel-sel jiran dipisahkan oleh partition mesh, secara keseluruhan terdapat n & minus; 1 partition dalam kandang. Pada mulanya, betul-betul seekor anak kucing dengan beberapa nombor ditempatkan dalam setiap sel.
Memerhati anak-anak kucing itu, Asya perasan bahawa mereka sangat mesra dan beberapa pasang anak kucing yang tinggal di sel berjiran sangat ingin bermain sesama sendiri. Untuk tidak menghalang mereka daripada keseronokan ini, Asya mula mengeluarkan sekatan antara sel bersebelahan, menjadikannya lebih besar.
Pada hari ke-i, Asya melakukan perkara berikut.
Saya perasan bahawa beberapa anak kucing x
i dan y
i, yang tinggal di sel jiran pada hari ke-i, mahu bermain.
Saya mengalih keluar pemisah antara sel ini, menjadikannya satu, di mana semua anak kucing dari dua sel sebelumnya berakhir.
Oleh kerana Asya tidak memulangkan sekatan, selepas n & tolak; 1 hari kandang menjadi satu sel di mana semua anak kucing tinggal. Memandangkan sangat pedantik, Asya menulis ID anak kucing x
i dan y
i untuk setiap n&tolak;1 hari dalam jurnal khas.
Anda mendapat majalah dengan maklumat ini, tetapi anda tidak tahu bagaimana anak kucing itu ditempatkan di dalam sel pada mulanya. Cari sebarang taburan anak kucing dalam n sel asal yang tidak bercanggah dengan data dalam log.
Input
Baris pertama mengandungi integer n (
\(2 \leq n \leq 150000\)) — bilangan anak kucing.
Baris n&tolak;1 seterusnya mengandungi pasangan integer x
i , y
i (
\(1 \leq x_i , y_i, \leq n,x_i \neq y_i\) ) — pengecam anak kucing, di antara sel-sel yang partitionnya telah dikeluarkan pada hari i. Ia dijamin bahawa anak kucing xi dan yi tidak berada dalam sel yang sama hasil daripada penggabungan sel sebelumnya.
Cetakan
Cetak n integer berbeza p
i (
\(1 \leq p_i \leq n\)), dengan p
i — pengecam anak kucing yang asalnya hidup dalam nombor sel i. Jika terdapat beberapa kemungkinan jawapan, cetak mana-mana daripadanya.
Nota
Dalam jawapan, sebagai contoh, salah satu kemungkinan penempatan awal anak kucing diberikan, terdapat jawapan lain. Imej di bawah menunjukkan cara sel digabungkan untuk penempatan awal anak kucing ini. Sila ambil perhatian bahawa dengan susunan ini, anak kucing yang menjadi kawan pada setiap hari mengikut jurnal Asya berada dalam sel bersebelahan.
| Input |
Output |
5
14
25
3 1
4 5 |
3 1 4 2 5 |