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

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

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

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

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