E. Цусан ахан дүүс

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Поликарпус ургийн модоо үзэж байна. Уг модонд $1$-с $n$ хүртэл дугаарлагдсан $n$ хүн байгаа бөгөөд хэн ч $1$-с олон олон эцэггүй.

Хэрвээ $a$ нь $b$-н эцэг бол $a$-г $b$-н $1$-р өвөг гэж нэрлэе.

Хэрвээ $a$ нь $b$-н $1$-р өвгийн $k-1$-р өвөг байх юм бол $a$-г $b$-н $k$ ($k > 1$)-р өвөг гэж үзнэ.

Ургийн модонд цикл байхгүй. Энэ нь өөрөө өөрийнхөө өвөг болдог хүн байхгүй гэсэн үг (шууд буюу шууд бусаар. Энэ нь өөрийнхөө $x$-р өвөг байх $x$, $x > 0 $ олдохгүй болно).

Хэрвээ $z$ нь $a$-н $x$-р өвөг, $y$-н $p$-р өвөг болж чадаж байвал $x$, $y$ ($x ≠ y$)-г $p$-р үеийн хамаатнууд ($p > 0$) гэнэ.

Оролт

Эхний мөр нийт хүний тоо $n$-г ($1 ≤ n ≤ 10^5$) агуулна. Дараагийн мөрөнд зайгаар тусгаарлагдсан $r_1, r_2, ... , r_n$ ($1 ≤ r_i ≤ n$) байх $n$ тоо өгөгдөнө. $r_i$ нь $i$-р хүний эцэг бөгөөд, хэрвээ $r_i$ нь $0$ байвал $i$ хүн эцэггүй болно. Энэ ургийн мод циклгүй байна.

Дараагийн мөрөнд Поликарпусын хүсэлтийн тоо $m$ ($1 ≤ m ≤ 10^5$) байна. $i$-р мөрөнд $v_i$, $p_i$ ($1 ≤ v_i, p_i ≤ n$) өгөгдөнө.

Гаралт

Нийт $m$ мөрөнд Поликарпусын хүсэлтийн хариунуудыг хэвлэнэ. Харилтуудыг оролтонд өгсөн дарааллаар хэвлээрэй.

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
6
0 1 1 0 4 4
7
1 1
1 2
2 1
2 2
4 1
5 1
6 1
Гаралт
0 0 1 0 0 1 1 
Сэтгэгдлүүдийг ачааллаж байна...