E. Үеэлүүдийн эргэн ирэлт

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

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

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

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

Поликарпус гэр бүлийн мод олсон. Олсон мод 1-с $n$ хүртэл дугаарлагдсан $n$ хүний гэр бүлийн холбоог тодорхойлно. Энэ модонд байгаа хүн бүр хамгийн ихдээ нэг шууд өвөгтэй. Мөн модон дахь хүн бүр нэртэй ба нэр нь давтагдашгүй байх албагүй.

Хэрвээ $a$ дугаартай хүн $b$ дугаартай хүний шууд өвөг байвал бид $a$ дугаартай хүнийг $b$ дугаартай хүний 1-өвөг гэж нэрлэнэ.

Хэрвээ $b$ дугаартай хүн 1-өвөгтэй ба $a$ дугаартай хүн $b$ дугаартай хүний 1-өвгийн $(k - 1)$-өвөг байвал бид $a$ дугаартай хүнийг $b$ дугаартай хүний $k$-өвөг $(k > 1)$ гэнэ.

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

Хэрвээ $b$ дугаартай хүн $a$ дугаартай хүний $k$-өвөг байвал бид $a$ дугаартай хүнийг $b$ дугаартай хүний $k$-хүү гэнэ.

Поликарпус хэдэн хүү байна вэ мөн хүн бүрт хэдэн хүү байна вэ гэдгийг маш их сонирхож байна. Тэр цаас аваад $m$ хос бүхэл тоо $v_{i}$, $k_{i}$ бичсэн. Түүнд $v_{i}$, $k_{i}$ хос тоо бүрийн хувьд $v_{i}$ дугаартай хүний $k_{i}$-хөвүүдийн нэрэн дундаас ялгаатай нэрүүдийн тоог олоход туслана уу.

Оролт

Оролтын эхний мөрөнд бүхэл тоо $n$ $(1 ≤ n ≤ 10^{5})$ байх ба гэр бүлийн модон дахь хүмүүсийн тоо. Дараагийн $n$ мөрөнд хүмүүсийн тайлбар байна. $i$-р мөрөнд зайгаар тусгаарлагдсан $s_{i}$ тэмдэгт мөр ба $r_{i}$ $(0 ≤ r_{i} ≤ n)$ бүхэл тоо байх ба энд $s_{i}$ нь $i$ дугаартай хүний нэр байна, харин $r_{i}$ нь хэрвээ $i$ дугаартай хүн шууд өвөггүй бол $0$ байна эсвэл шууд өвгийн дугаар байна.

Дараагийн мөрөнд нэг бүхэл тоо $m$ $(1 ≤ m ≤ 10^{5})$ байх ба Поликарпусийн бичлэгүүдийн тоо юм. Дараагийн $m$ мөрөнд зайгаар тусгаарлагдсан хос бүхэл тоо байна. $i$-р мөрөнд $v_{i}$, $k_{i}$ $(1 ≤ v_{i}, k_{i} ≤ n)$ бүхэл тоонууд байна.

Гэр бүлийн холбоосууд цикл үүсгэхгүй. Бүх хүний нэр хоосон биш, Англи цагаан толгойн 20-с ихгүй үсэгтэй тэмдэгт мөр байна.

Гаралт

Поликарпусийн бичлэгүүдийн хариултуудыг илэрхийлэх зайгаар тусгаарлагдсан $m$ бүхэл тоог хэвлэ. Бичлэгүүдийн хариултуудыг тэдгээрийн оролтонд өгсөн дарааллаар хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
6
pasha 0
gerald 1
gerald 1
valera 2
igor 3
olesya 1
5
1 1
1 2
1 3
3 1
6 1
Гаралт
2
2
0
1
0
Оролт
6
valera 0
valera 1
valera 1
gerald 0
valera 4
kolya 4
7
1 1
1 2
2 1
2 2
4 1
5 1
6 1
Гаралт
1
0
0
0
2
0
0
Сэтгэгдлүүдийг ачааллаж байна...