Problem
Asya hayvanları çok sever. Yakın zamanda n kedi yavrusu satın aldı, onlara 1'den n'ye kadar sayısal tanımlayıcılar verdi ve onları bir muhafazaya yerleştirdi. Kuş kafesi, yine 1'den n'ye kadar numaralandırılmış n hücrelik bir sıradır. Komşu hücreler kafes bölmelerle ayrılmıştır, toplamda muhafazada n ve eksi 1 bölme vardır. Başlangıçta, her hücreye bir numara ile tam olarak bir yavru kedi yerleşti.
Yavru kedileri izleyen Asya, onların çok cana yakın olduklarını ve komşu hücrelerde yaşayan bazı kedi yavrularının gerçekten birbirleriyle oynamak istediklerini fark etti. Asya, onları bu zevkten mahrum bırakmamak için bitişik hücreler arasındaki bölmeleri kaldırarak büyütmeye başladı.
1. gün Asya şunları yaptı.
Komşu hücrelerde i. günde yaşayan x
i ve y
i adlı bazı yavru kedilerin oyun oynamak istediğini fark ettim.
Bu hücreler arasındaki bölmeyi kaldırdım ve onları, önceki iki hücredeki tüm kedi yavrularının son bulduğu tek bir hücreye dönüştürdüm.
Asya bölmeleri iade etmediği için n & eksi 1 gün sonra muhafaza, tüm yavru kedilerin yaşadığı tek bir hücreye dönüştü. Çok bilgiçlik yapan Asya, kedi yavrusu kimliklerini x
i ve y
i her n&minus1 gün için özel bir günlüğe yazdı.
Bu bilgilerin olduğu bir derginiz var ama ilk etapta yavru kedilerin hücrelere nasıl yerleştirildiğini bilmiyorsunuz. Günlükteki verilerle çelişmeyen n orijinal hücrede herhangi bir yavru kedi dağılımı bulun.
Girdi
İlk satır bir tamsayı içerir n (
\(2 \leq n \leq 150000\)) — kedi sayısı.
Sonraki n−1 satır, x
i , y
i (
\(1 \leq x_i) tamsayı çiftlerini içerir , y_i, \leq n,x_i \neq y_i\) ) — i. günde bölmenin kaldırıldığı hücreler arasında yavru kedi tanımlayıcıları. Yavru kedi xi ve yi önceki hücre birleştirme sonucunda aynı hücrede olmadığı garanti edilir.
Künye
n farklı tam sayı p
i (
\(1 \leq p_i \leq n\)) yazdırın, burada p
i — i numaralı hücrede yaşayan yavru kedinin tanımlayıcısı. Birkaç olası cevap varsa, herhangi birini yazdırın.
Not
Cevapta mesela yavru kedilerin olası ilk yerleşim yerlerinden biri veriliyor, başka cevaplar da var. Aşağıdaki resim, yavru kedilerin bu ilk yerleşimi için hücrelerin nasıl birleştirildiğini göstermektedir. Lütfen bu düzenleme ile Asya'nın günlüğüne göre her gün arkadaş olan yavru kedilerin yan hücrelerde olduğunu unutmayın.
| Giriş |
Çıktı |
5
14
25
3 1
4 5 |
3 1 4 2 5 |