Problem
Bir sonraki, zaten 13. uluslararası Olimpiyata katılan Konstantin, trenle eve dönüyordu. Her zaman olduğu gibi oturdu ve hayatın anlamı hakkında düşündü, aynı anda programlama problemlerini çözdü. Bir süre sonra Konstantin uyuyakaldı ama sorun şu ki, uyanmak için kafasında beliren ve onu rahatsız eden sorunu çözmesi gerekiyor!
Bu sefer Konstantin, başlangıçta yalnızca 1 numaralı bir tepe noktasından oluşan bir ağaç hayal etti. Kurduğu problemde, ağaca yavaş yavaş yeni köşeler eklendi. i. saniyede p
i tepe noktasından oğul olarak asılı duran ve i+1 köşeleri arasındaki kenarda bulunan ağaca i+1 numaralı bir tepe eklendi. ve c
i harfinin yazıldığı p
i.
Ağacın kökünden v tepe noktasına kadar olan her yol, mevcut yolun kenarlarına yazılan sembollerin kökten v tepe noktasına sırasıyla yazılmasıyla elde edilen belirli bir diziye karşılık gelir. Konstantin ilk bakışta zor bir görevle karşı karşıya kaldı - her yeni köşe noktası eklendikten sonra, ağacın kökünden (köşe numarası 1) başlayan ve başka bir köşede biten benzersiz dizilerin sayısını sayın.
Konstantin rüyasında hiç de dahi değildir, bu yüzden bu sorunu kendisi çözemez. Konstantin'in sorunu çözmesine ve uyanmasına yardım et.
Giriş:
İlk satır, ağaca yeni bir düğüm eklemek için istek sayısı olan n sayısını içerir (1 <= n <= 300000).
Sonraki n satır, köşe ekleme isteklerini açıklar. i'nci sorgu, p
i (1 <= p
i <= i) ve c
i parametreleriyle tanımlanır; eklenen i+1 numaralı köşenin p
i numaralı köşeden çocuk olarak askıya alındığı ve elde edilen kenara c
i sembolünün yazıldığı anlamına gelir - latin alfabesinin küçük harfi.
Çıktı:
n satır yazdır. i'nci satıra, i+1'inci tepe noktasını ekledikten sonra Konstantin'in probleminin cevabını yazdırın.
Örnekler:
| Giriş |
Çıktı |
2
1 b
2p |
1
2 |
3
1 o
1 o
2 j |
1
1
2 |