Sane's Monthly Algorithms Challenge: November 2008
The hypothesis known as the 6 Degrees of Separation suggests that everyone knows everyone else through an average chain of people.
But if we only consider chains linked together by best friends, then this hypothesis severely breaks down. In many cases, we even obtain "infinite degrees of separation", when two people can not be linked together at all by such a chain.
We would like to demonstrate this on some sample data. Given a list of who considers whom to be their best friend, we would like to know for particular pairs of people, how many unique chains can be formed to join the two together (e.g. If the number of unique chains is zero, then there are infinite degrees of separation between the two people).
A link in a chain can either be a person and his/her best friend, or a best friend and the person who considers him/her to be their best friend. The uniqueness of a chain is determined by its set of links, and a valid chain can not use the same person more than once.
Input Specification
The first line of the input consists of two integers, , and , representing the number of people in the sample data, and the number of query pairs, respectively.
The next lines (line : ) that follow will each contain a single integer (, excluding ). This line states that the person considers the person to be his or her best friend.
The next lines that follow will each contain two integers and , representing a question about the number of unique chains which exist between person and person .
Output Specification
In lines, respond to each question (in order) with an integer representing the number of unique chains which exist between the two people.
Sample Input
10 3
1
2
3
4
1
3
5
8
9
7
0 4
5 6
6 9
Sample Output
2
1
0
Comments
If 's best friend is , and 's best friend is , then there are 2 different links between and .