Se dă un arbore cu N noduri numerotate de la 1 la N, înrădăcinat în nodul 1. O mutare de cal dintr-un nod u către un nod v constă în parcurgerea unui traseu u → x → y → v, unde x este părintele lui u, y este părintele lui v, iar v este un fiu al lui y astfel încât v ≠ x (vezi imaginea). Observăm cum mutarea se aseamănă unei mutări de cal pe tabla de șah.

Cerința

Date fiind N și părinții fiecărui nod P2, . . . , Pn (nodul 1, fiind rădăcina, nu are părinte), să se determine:

1. Numărul de noduri cu exact un fiu.

Date fiind, în plus, Q perechi de noduri, să se determine pentru fiecare pereche dată (a, b):

2. Dacă se poate ajunge din nodul a în nodul b făcând succesiv mutări de cal. În caz afirmativ, răspunsul va fi 1, altfel 0.
3. Numărul de trasee distincte ce pornesc din nodul a și ajung în nodul b făcând succesiv mutări de cal. Deoarece răspunsul poate fi destul de mare, se cere restul împărțirii acestuia la 109 + 7.

Date de intrare

Fișierul de intrare knight.in conține prima linie va conține numărul cerinței C ∈ {1, 2, 3}. A doua linie va conține numărul de noduri din arbore N. A treia linie va conține N − 1 numere P2, . . . , Pn, reprezentând părintele fiecărui nod din arbore (nodul 1, fiind rădăcina, nu are părinte). Oricare două numere consecutive de pe această linie sunt separate prin câte un spațiu. Doar dacă C ∈ {2, 3}, a patra linie va conține numărul de perechi Q, următoarele Q linii conținând numerele a și b, separate printr-un spațiu, corespunzătoare fiecărei perechi (a, b).

Date de ieșire

Dacă C = 1, fișierul de ieșire knight.out va conține pe o singură linie numărul de noduri cu exact un fiu. Dacă C∈{2, 3} fișierul de ieșire knight.out va conține Q linii, fiecare conținând răspunsul la cerința C corespunzator câte unei perechi a b din cele Q date.

Restricții și precizări

• C ∈ {1, 2, 3}
• 1 ≤ N ≤ 200 000
• 1 ≤ P[i] < N pentru 2 ≤ i ≤ N
• Dacă C ∈ {2, 3}, atunci:
  • 1 ≤ Q ≤ 200 000
  • 1 ≤ a, b ≤ N și a ≠ b, pentru fiecare dintre cele Q perechi date.
• Pentru C = 3, două trasee s[1] → s[2] → ... → s[k] și t[1] → t[2] → ... → t[f] se consideră diferite dacă k ≠ f sau dacă există 1 ≤ i ≤ k astfel încât s[i] ≠ t[i].

Subtaskuri

1. pentru 56 de puncte: C = 1;
2. pentru 9 puncte: C = 2 și N ≤ 100;
3. pentru 6 puncte: C = 2;
4. pentru 5 puncte: C = 3 și N ≤ 100;
5. pentru 8 puncte: C = 3 și pentru fiecare pereche dată numărul de trasee este nenul;
6. pentru 6 puncte: C = 3 și pentru fiecare pereche dată P[b] = 1;
7. pentru 10 puncte: C = 3.

Exemplul 1

knight.in

1
7
1 1 3 3 3 4

knight.out

1

Exemplul 2

knight.in

2
7
1 1 3 3 3 4
3
7 2
7 4
6 2

knight.out

1
0
1

Exemplul 3

knight.in

3
7
1 1 3 3 3 4
3
7 2
7 4
6 2

knight.out

2
0
1

Explicații

Cele trei exemple vizează același arbore cu N = 7 noduri, schițat mai jos:

Primul exemplu. Singurul nod din arborele de mai sus care are exact un fiu este nodul 4.

Al doilea și al treilea exemplu. Singura diferență între cele două exemple este numărul cerinței de rezolvat C ∈ {2, 3}. Sunt date Q = 3 perechi de noduri (a, b):

1. a = 7, b = 2: Există două trasee ce pleacă din 7 și ajung în 2 prin mutări de cal:

(a) 7 → 4 → 3 → 5 → 3 → 1 → 2 (compus din două mutări de cal colorate diferit și evidențiate în figură)
(b) 7 → 4 → 3 → 6 → 3 → 1 → 2

Așadar, pentru C = 2 răspunsul este 1, iar pentru C = 3 este 2.

2. a = 7, b = 4: Nu există niciun traseu ce pleacă din nodul 7 și ajunge în nodul 4 prin mutări succesive de cal, de unde răspunsul pentru ambele cerințe este 0.

3. a = 6, b = 2: Există un singur traseu ce pleacă din 6 și ajunge în 2 prin mutări de cal, anume:
(a) 6 → 3 → 1 → 2
Prin urmare, răspunsul pentru ambele cerințe este 1.