Bạn đang chơi một trò chơi bao gồm \(n\) hành tinh. Mỗi hành tinh có một cổng dịch chuyển đến một hành tinh khác (hoặc chính hành tinh đó).

Nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: Bây giờ bạn đang ở hành tinh \(a\) và muốn đến hành tinh \(b\). Số lần dịch chuyển tối thiểu là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(q\): số lượng hành tinh và truy vấn. Các hành tinh được đánh số \(1,2,\ldots,n\).
• Dòng thứ hai có \(n\) số nguyên \(t_1,t_2,\ldots,t_n\): với mỗi hành tinh, điểm đến của của cổng dịch chuyển. Có thể là \(t_i=i\).
• Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có hai số nguyên \(a\) và \(b\): bây giờ bạn đang ở hành tinh \(a\) và muốn đến hành tinh \(b\).

Output

• Với mỗi truy vấn, in số lần dịch chuyển tối thiểu. Nếu không thể đến đích, hãy in \(−1\).

Constraints

• \(1 \leq n, q \leq 2 \cdot 10 ^ 5\)
• \(1 \leq t_i \leq n\)
• \(1 \leq a, b \leq n\)

Example

Sample input

5 3
2 3 2 3 2
1 2
1 3
1 4

Sample output

1
2
-1