მეგალოპოლისი

დროის ლიმიტი: 2 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: პოლონეთი, ოლიმპიადა 14, ეტაპი 2


გლობალიზაციამ საბოლოოდ ბაიტოტიამდე და მასში მცხოვრებ ფოსტალიონ ბაიტეზარამდეც კი მიაღწია. ფოსტალიონი ახლა უკვე მიჩვეულია საავტომობილო გზებზე სიარულს, მაგრამ მისთვის ნამდვილ სიტკბოობასა და კეთილ მოგონებას ძველი დღეები წარმოადგენენ, როდესაც იგი სოფლებს შორის მიწის გზებით დასეირნობდა ხოლმე.

 

ძველად ბაიტოტიის n სოფელი (გადანომრილი 1-იდან n-მდე) ერთმანეთთან ორმხრივი მიწის, ბუნებრივი გზებით ისე იყო დაკავშირებული, რომ ნებისმიერი სოფლიდან სოფელ 1-ში (ბიტბურგში) ჩასვლა მხოლოდ და მხოლოდ ერთი მარშრუტით შეიძლებოდა. ეს უნიკალური მარშრუტი მხოლოდ ისეთ სოფლებს გადიოდა, რომლების ნომრებიც არ აღემატებოდა საწყისი სოფლის ნომერს. ამასთან დამატებით, ყოველი გზა ზუსტად ორ განსხვავებულ სოფელს სხვა სოფლების გავლისა და გადაკვეთის გარეშევე აკავშირებდა ერთმანეთთან. გზები სოფლებს გარეთ არ გადიოდა, მაგრამ გვირაბები და ვიადუკები გაუგონარი ნამდვილად არ იყო.

 

დროის გასვლასთან ერთად მიწის გზებს საავტომობილო გზებით ანაცვლებდნენ. ბაიტეზარს ზუსტად ახსოვს, თუ რომელი გზის გადაკეთება რა დროს მოხდა. დღეისთვის ბაიტოტიაში არცერთი მიწის გზა არაა დარჩენილი - ყველა საავტომობილო გზით არის ჩანაცვლებული, რომლებიც სოფლებს ბაიტოტიის მეგალოპოლისთან აკავშირებს.

 

ბაიტეზარს ასევე კარგად ახსოვს მისი მოგზაურობები. ყოველ მოგზაურობისას იგი რომელიმე სოფელში ფოსტების ჩასატანად ჩადიოდა ხოლმე. ფოსტალიონს აინტერესებს, ყოველი ასეთი მოგზაურობის დროს (რომელიც დროის გარკვეულ მომენტში მოხდა და ბიტბურგიდან დაწყებული აღნიშნულ სოფელში დასრულდა), რამდენი მიწის გზის გავლა მოუხდა მას?

 

დაწერეთ პროგრამა, რომელიც:

 

  • კითხულობს მონაცემებს stdin-იდან:
  • გზებს, რომლებიც ერთ დროს ბაიტოტიის სოფლებს ერთმანეთთან აკავშირებდა,
  • მოვლენების მიმდოვრობას: ბაიტეზარის მოგზაურობები და მომენტები, როდესაც გარკვეული გზები საავტომობილო გზებად გადაკეთდა.
  • თითოეული მოგზაურობისთვის გამოთვალეთ, თუ რამდენი მიწის გზის გავლა მოუხდა ბაიტეზარს.
  • პასუხი დაბეჭდეთ stdout-ში.

 

შემოსატანი მონაცემები:

 

შემომავალი ინფორმაციიდან პირველ ხაზზე წერია ერთი რიცხვი n (1 <= n <= 250 000), რომელიც ბაიტოტიის სოფლების რაოდენობას აღნიშნავს. მომდევნო n - 1 ხაზზე განთავსებულია გზების ინფორმაცია, ორი რიცხვის სახით a, b (1 <= a < b <= n). შემდეგ ხაზზე წერია რიცხვი m (1 <= m <= 250 000), რომელიც ბაიტეზარის მოგზაურობების რაოდენობას აღნიშნავს. მომდევნო n + m - 1 ხაზი კი ქრონოლოგიურად განვითარებულ მოვლენებს აღნიშნავს:

 

  • A a b (a < b) აღნიშნავს ამ კონკრეტულ მომენტში a და b სოფლებს შორის არსებული გზის საავტომობილო გზით ჩანაცვლებას.
  • W a აღნიშნავს ბაიტეზარის მოგზაურობებს ბიტბურგიდან სოფელ a-მდე.

 

გამოსატანი მონაცემები:

 

თქვენმა პროგრამამ უნდა დაბეჭდოს ზუსტად 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 დაკოპირება