Module: हैशिंग

Problem

एक बार कॉन्स्टेंटिन, अगले 13 वें अंतर्राष्ट्रीय ओलंपियाड में भाग लेने के बाद, ट्रेन से घर लौट रहा था। वह, हमेशा की तरह, बैठे और जीवन के अर्थ के बारे में सोचा, साथ ही साथ प्रोग्रामिंग समस्याओं को हल किया। कुछ समय बाद, कॉन्स्टेंटिन को नींद आ गई, लेकिन समस्या यह है कि जागने के लिए, उसे उस समस्या का समाधान करना होगा जो उसके सिर में उठी है, जो उसे परेशान करती है!

इस बार, कॉन्स्टेंटिन ने एक ऐसे पेड़ का सपना देखा, जिसमें शुरू में नंबर 1 के साथ केवल एक शीर्ष शामिल था। उसने जो समस्या निर्धारित की, उसमें नए कोने धीरे-धीरे पेड़ में जुड़ गए। i-वें सेकंड में, संख्या i+1 के साथ एक शीर्ष पेड़ में जोड़ा गया था, जो शीर्ष p_i से एक बेटे के रूप में निलंबित कर दिया गया था, और शीर्षों के बीच किनारे पर i+1 और p_i अक्षर c_{i लिखा गया था।}

पेड़ की जड़ से शीर्ष v तक का प्रत्येक पथ एक निश्चित स्ट्रिंग से मेल खाता है जो रूट से शीर्ष v के क्रम में वर्तमान पथ के किनारों पर लिखे गए प्रतीकों को लिखकर प्राप्त किया जाता है। कॉन्स्टेंटिन को पहली नज़र में एक मुश्किल काम का सामना करना पड़ा - एक नए शीर्ष के प्रत्येक जोड़ के बाद, पेड़ की जड़ (शीर्ष संख्या 1) से शुरू होने वाले और किसी अन्य शीर्ष पर समाप्त होने वाले अद्वितीय तारों की संख्या की गणना करें। 

अपने सपने में, कॉन्स्टेंटिन बिल्कुल भी प्रतिभाशाली नहीं है, इसलिए वह स्वयं इस समस्या को हल नहीं कर सकता है। कॉन्स्टेंटिन की समस्या को हल करने और जागने में मदद करें।

इनपुट:
पहली पंक्ति में संख्या n है - ट्री में एक नया नोड जोड़ने के अनुरोधों की संख्या (1 <= n <= 300000)।
अगली n पंक्तियाँ वर्टिकल जोड़ने के अनुरोधों का वर्णन करती हैं। i-th क्वेरी पैरामीटर p_i (1 <= p_i <= i) और c_i द्वारा वर्णित है, जो इसका मतलब है कि नंबर i+1 के साथ जोड़ा गया शीर्ष नंबर p_i के साथ एक बच्चे के रूप में शीर्ष से निलंबित कर दिया गया है, और प्रतीक c_i परिणामी किनारे पर लिखा गया है - लैटिन वर्णमाला का एक छोटा अक्षर।

आउटपुट:
एन लाइन प्रिंट करें। i+1-वें शीर्ष को जोड़ने के बाद i-वें पंक्ति पर Konstantin की समस्या का उत्तर प्रिंट करें।

उदाहरण:
  <तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;"> <शरीर> इनपुट आउटपुट 2
1 ख
2p 1
2 3
1 ओ
1 ओ
2 जे 1
1
2