Невероятно трудно одному человеку изучить всю галактическую историю.

С другой стороны каждый дипломат, стремящийся занять как более значимый пост в галактической империи, должен очень хорошо ее знать. Так уронить ложку в присутствии высокопоставленных членов звездной системы Арктура, значит неслыханно их оскорбить (А разве вы не слышали, что последний конфликт между системами Арктура и Альфы Водолея разгорелся всего то из-за одного уроненного стакана).

К счастью в Галактической Академии выяснили, что, например, для дипломатов нижнего ранга достаточно выучить только одну ветвь истории, касающуюся только того кластера звездных систем, в котором он собирается работать. (Действительно, ведь дипломаты нижнего ранга ведут переговоры только между планетами, находящимися в одном звездном кластере. И как нам раньше не приходила такая идея).

С учетом этого очень ценного замечания было решено единый межгалактический курс истории заменить на несколько локализованных курсов, каждый из которых охватывает только ту часть истории, которая касается только одного звездного кластера. Естественно, что историю изучать надо в хронологическом порядке, начиная от зарождения человечества, поэтому историю Земли нужно включить во все сборники локализованных историй. Дальше сложнее: так звездная система Волопаса была колонизирована выходцами из системы Центавры, а значит учебник для системы Волопаса обязательно должен включать раннюю историю системы Центавра.

Для решения вопроса о том, какие этапы истории включать или не включать в тот или иной учебник, специалисты-историки Галактической Академии разбили всеобщую межгалактическую историю на множество мелких вех. Далее все вехи были построены в одно большое дерево (тут помогли вездесущие биологи, которые, как оказалось, всегда пользовались такими деревьями). Корнем этого дерева была объявлена веха, соответствующая ранней истории Земли (до космической колонизации). Ее сыновьями являются вехи, которые соответствуют истории Звездных систем, близких к Солнечной системе (так как они были колонизированы выходцами с Земли) и т.д. Все! Для определения тех вех, которые стоит включать в учебник, осталось всего-навсего быстро определять, находится ли веха A в поддереве с корнем в вехе B.

В первой строке находится число N (N ≤ 40000), определяющее общее число вех. В следующих N строках находятся описания каждой из вех.

Каждая веха описывается двумя числами: ID - уникальный числовой идентификатор вехи и ParentID - идентификатор вехи, являющейся ее отцом в данном дереве. (ParentID для корня дерева равен -1).

(N+2)-я строка содержит число L (L ≤ 40000) - количество запросов. Следующие L строк содержат описания запросов: два различных числа A и B. Все идентификаторы лежат в пределах от 0 до 40000.

Для каждого запроса в отдельной строке необходимо вывести:

• 1, если веха А является корнем поддерева, содержащего веху B.
• 2, если веха B является корнем поддерева, содержащего веху A.
• 0, если не верно ни одно из первых двух условий.