CF208E Blood Cousins

Polycarpus got hold of a family relationship tree. The tree describes family relationships of $ n $ people, numbered 1 through $ n $ . Each person in the tree has no more than one parent. Let's call person $ a $ a 1-ancestor of person $ b $ , if $ a $ is the parent of $ b $ . Let's call person $ a $ a $ k $ -ancestor $ (k>1) $ of person $ b $ , if person $ b $ has a 1-ancestor, and $ a $ is a $ (k-1) $ -ancestor of $ b $ 's 1-ancestor. Family relationships don't form cycles in the found tree. In other words, there is no person who is his own ancestor, directly or indirectly (that is, who is an $ x $ -ancestor for himself, for some $ x $ , $ x>0 $ ). Let's call two people $ x $ and $ y $ $ (x≠y) $ $ p $ -th cousins $ (p>0) $ , if there is person $ z $ , who is a $ p $ -ancestor of $ x $ and a $ p $ -ancestor of $ y $ . Polycarpus wonders how many counsins and what kinds of them everybody has. He took a piece of paper and wrote $ m $ pairs of integers $ v_{i} $ , $ p_{i} $ . Help him to calculate the number of $ p_{i} $ -th cousins that person $ v_{i} $ has, for each pair $ v_{i} $ , $ p_{i} $ .

N/A

N/A