Гарагуудын хүсэлт II

2s

512MB

1363

0%

Graph Algorithms

$n$ гараг бүхий тоглоом тоглож байна. Гараг бүр өөр гараг (эсвэл өөрөө) рүү телепортлогчтой.

Дараах хэлбэрийн $q$ хүсэлтийг боловсруул: $a$ гараг дээр байгаа бөгөөд $b$ гарагт хүрэхийг хүсэж байна. Хамгийн багадаа хэдэн телепорт хэрэгтэй вэ?

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд $n$ ба $q$ хоёр бүхэл тоо байна: гараг болон хүсэлтийн тоо. Гарагууд $1,2,\ldots,n$ гэж дугаарлагдсан.

Хоёр дахь мөрөнд $n$ бүхэл тоо $t_1,t_2,\ldots,t_n$ байна: гараг бүр дээрх телепортын очих цэг.

Дараа нь хүсэлтүүдийг тодорхойлсон $q$ мөр байна. Мөр бүрт $a$ ба $b$ хоёр бүхэл тоо байна: одоо $a$ гараг дээр байгаа бөгөөд $b$ гарагт хүрэхийг хүсэж байна.

Гаралтын формат

Хүсэлт бүрт хамгийн бага телепортын тоог хэвлэ. Очих боломжгүй бол $-1$ хэвлэ.

Хязгаарлалт

$1 \le n, q \le 2 \cdot 10^5$
$1 \le a,b \le n$

Жишээ

Оролт1

Гаралт1

1
2
-1

0.1 / 64 KiB

Редактор уншиж байна...