It is very hard for one person to learn all galactic history. But, on the other hand, every diplomat who wants to hold a more important post in a galactic empire must know the subject well. For example, letting a spoon fall among high-rankers of the star system Arcturus means offending them awfully. (Didn’t you hear that the last conflict between systems Arcturus and Alpha flamed up because of the only shattered glass?)

Fortunately, the solution was found in the Galactic Academy. For diplomats of the lower rank it is enough to learn just a single branch of history – the one that concerns only the cluster of star systems, in which he is going to work. (Diplomats of the lower rank negotiate only with planets that are located in one star cluster. How come we didn’t guess this earlier?)

Taking this very important observation into consideration, it was decided to replace a single intergalactic course with several separate courses, each covering only the part of history that refers to only one star cluster. Of course, it is necessary to learn history in chronological order, beginning from the origin of humanity. That’s why the history of the Earth needs to be included in all collections of separate histories. Then things become complicated: for example, emigrants from Centaurus system colonized the star system of Herdsman, so the textbook on the history of Herdsman system has to contain the early history of Centaurus system. In order to decide, in which textbooks which phases of history should be included, historians of Galactic Academy divided general intergalactic history into many small milestones. Then all milestones were combined into one big tree (omnipresent biologists helped historians in this work, as they had always been using these trees). The milestone referring to early history of the Earth (before the space colonization) was declared the root. Milestones referring to history of star systems close to solar system appear to be its sons (because these systems were colonized by emigrants from Earth) and so on. That’s all! To determine milestones that have to be included in a particular textbook it is only required to determine quickly, whether the milestone A is located in a subtree with the root in milestone B.

In the first line there is a number N (N ≤ 40000), which defines the total number of milestones. In the next N lines there are descriptions of each milestone.

Each milestone is defined by two numbers: ID – an unique numerical identifier of a milestone and ParentID – identifier of the milestone which is its father in a tree. ParentID for the root equals to -1.

(N+2)^th line contains number L (L ≤ 40000) – amount of queries. The next L lines contain descriptions of queries: on each line there are two different numbers A and B. All identifiers lie between 0 and 40000.

For each query it is necessary to write in separate line:

• 1, if milestone A is a root of subtree which contains milesone B.
• 2, if milestone B is a root of subtree which contains milesone A.
• 0, if no one of the first two conditions is true.