PEG Judge - SMAC 08/09 (Nov) #4

Sane's Monthly Algorithms Challenge: November 2008

Infinite Degrees of Separation (Advanced Level)

The hypothesis known as the 6 Degrees of Separation suggests that everyone knows everyone else through an average chain of 6 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

The first line of the input consists of two integers, n (1 ≤ n ≤ 100,000), and m (1 ≤ m ≤ 100,000), representing the number of people in the sample data, and the number of query pairs, respectively.

The next n lines (line i : 0 ≤ i ≤ n-1) that follow will each contain a single integer j ∈ [0, n-1] \ {i} (0 .. n-1, discluding i). This line states that the i'th person considers the j'th person to be his or her best friend.

The next m lines that follow will each contain two integers i and j (0 ≤ i, j ≤ n-1, i ≠ j), representing a question about the number of unique chains which exist between person i and person j.