Hành Tinh (Truy vấn II)

Có $n$ hành tinh, mỗi hành tinh có một cổng dịch chuyển tức thời đến một hành tinh khác (có thể là chính nó). Cho $q$ truy vấn, mỗi truy vấn hỏi: số bước dịch chuyển tối thiểu để đi từ hành tinh $a$ đến hành tinh $b$. Nếu không thể đến được, in $-1$.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $q$.
• Dòng 2: $n$ số nguyên $t_1,t_2,\dots ,t_n$ — hành tinh đích của cổng dịch chuyển tại mỗi hành tinh.
• $q$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a$ và $b$.

Dữ liệu ra

In $q$ số nguyên, mỗi số trên một dòng.

Ràng buộc

• $1\le n,q\le 2\times {10}^5$
• $1\le t_i\le n$
• $1\le a,b\le n$

Ví dụ