უცნაური შაში

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

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

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

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

წყარო: IBSU, 2015, ზამთრის ოლიმპიადა, XI-XII


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

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

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

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

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

დაწერეთ პროგრამა, რომელიც დაადგენს რამდენ პარტიას მოიგებს პირველი მოთამაშე, თუ ორივე მათგანი ოპტიმალურად თამაშობს.

შესატანი მონაცემები: სტანდარტული შეტანის პირველ სტრიქონში მოცემულია ერთი  მთელი დადებითი N რიცხვი (1≤N≤500 000) ხის წვეროთა რაოდენობა. მეორე სტრიქონში ჩაწერილია თითო ჰარით გამოყოფილი მთელი p2,  p3, ..., pN  რიცხვები, სადაც pi იმ წვეროს ნომერია, რომელიც i წვეროს (1≤pi<i)  მშობელს წარმოადგენს.

გამოსატანი მონაცემები: სტანდარტულ გამოტანაში უნდა გამოიტანოთ ერთადერთი მთელი რიცხვი - პირველი მოთამაშის მიერ მოგებული პარტიების რაოდენობა.




მაგალითები

შესატანი მონაცემები
7 1 2 3 1 5 5 დაკოპირება
გამოსატანი მონაცემები
3 დაკოპირება