დროის ლიმიტი: 2 წმ
მეხსიერების ლიმიტი: 64 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
წყარო: პოლონეთი, ოლიმპიადა 14, ეტაპი 2
გლობალიზაციამ საბოლოოდ ბაიტოტიამდე და მასში მცხოვრებ ფოსტალიონ ბაიტეზარამდეც კი მიაღწია. ფოსტალიონი ახლა უკვე მიჩვეულია საავტომობილო გზებზე სიარულს, მაგრამ მისთვის ნამდვილ სიტკბოობასა და კეთილ მოგონებას ძველი დღეები წარმოადგენენ, როდესაც იგი სოფლებს შორის მიწის გზებით დასეირნობდა ხოლმე.
ძველად ბაიტოტიის n სოფელი (გადანომრილი 1-იდან n-მდე) ერთმანეთთან ორმხრივი მიწის, ბუნებრივი გზებით ისე იყო დაკავშირებული, რომ ნებისმიერი სოფლიდან სოფელ 1-ში (ბიტბურგში) ჩასვლა მხოლოდ და მხოლოდ ერთი მარშრუტით შეიძლებოდა. ეს უნიკალური მარშრუტი მხოლოდ ისეთ სოფლებს გადიოდა, რომლების ნომრებიც არ აღემატებოდა საწყისი სოფლის ნომერს. ამასთან დამატებით, ყოველი გზა ზუსტად ორ განსხვავებულ სოფელს სხვა სოფლების გავლისა და გადაკვეთის გარეშევე აკავშირებდა ერთმანეთთან. გზები სოფლებს გარეთ არ გადიოდა, მაგრამ გვირაბები და ვიადუკები გაუგონარი ნამდვილად არ იყო.
დროის გასვლასთან ერთად მიწის გზებს საავტომობილო გზებით ანაცვლებდნენ. ბაიტეზარს ზუსტად ახსოვს, თუ რომელი გზის გადაკეთება რა დროს მოხდა. დღეისთვის ბაიტოტიაში არცერთი მიწის გზა არაა დარჩენილი - ყველა საავტომობილო გზით არის ჩანაცვლებული, რომლებიც სოფლებს ბაიტოტიის მეგალოპოლისთან აკავშირებს.
ბაიტეზარს ასევე კარგად ახსოვს მისი მოგზაურობები. ყოველ მოგზაურობისას იგი რომელიმე სოფელში ფოსტების ჩასატანად ჩადიოდა ხოლმე. ფოსტალიონს აინტერესებს, ყოველი ასეთი მოგზაურობის დროს (რომელიც დროის გარკვეულ მომენტში მოხდა და ბიტბურგიდან დაწყებული აღნიშნულ სოფელში დასრულდა), რამდენი მიწის გზის გავლა მოუხდა მას?
შემომავალი ინფორმაციიდან პირველ ხაზზე წერია ერთი რიცხვი n (1 <= n <= 250 000), რომელიც ბაიტოტიის სოფლების რაოდენობას აღნიშნავს. მომდევნო n - 1 ხაზზე განთავსებულია გზების ინფორმაცია, ორი რიცხვის სახით a, b (1 <= a < b <= n). შემდეგ ხაზზე წერია რიცხვი m (1 <= m <= 250 000), რომელიც ბაიტეზარის მოგზაურობების რაოდენობას აღნიშნავს. მომდევნო n + m - 1 ხაზი კი ქრონოლოგიურად განვითარებულ მოვლენებს აღნიშნავს:
თქვენმა პროგრამამ უნდა დაბეჭდოს ზუსტად m რაოდენობის რიცხვი, თითო თითო ხაზზე, რომლებიც აღნიშნავენ, თუ რამდენი მიწის გზა გაიარა ბაიტეზარმა მისი მოგზაურობების დროს.
შესატანი მონაცემები
5 1 2 1 3 1 4 4 5 4 W 5 A 1 4 W 5 A 4 5 W 5 W 2 A 1 2 A 1 3 დაკოპირება
გამოსატანი მონაცემები
2 1 0 1 დაკოპირება