e-olymp
Yarışlar

ADA Classes - Depth First Search

Parent

Write a program that determines for two nodes of a tree whether the first one is a parent of another.

Input

The first line contains the number of vertices n (1n100000) in a tree. The second line contains n numbers, the i-th one gives the vertex number of direct ancestor for the vertex i. If this value is zero, then the vertex is a root of a tree.

The third line contains the number of queries m (1m100000). Each of the next m lines contains two different numbers a and b (1a, bn).

Output

For each of the m queries print on a separate line number 1, if the vertex a is one of the parents of a vertex b, and 0 otherwise.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
3
2 0 2
10
1 3
2 3
3 1
2 3
3 2
2 1
3 2
3 2
3 1
3 2
Çıxış verilənləri #1
0
1
0
1
0
1
0
0
0
0
Müəllif Vitaly Goldstein
Mənbə Winter School, Kharkov, 2011, Day 9