Cho đồ thị hàm số gồm \(N\) đỉnh được đánh số từ \(0\) đến \(N-1\). Mỗi đỉnh \(i\) có đúng một cung đi ra hướng tới \(next[i]\).

Bạn cần xử lý \(Q\) truy vấn: Cho hai đỉnh \(U\) và \(V\), tìm số bước đi ít nhất để đi từ \(U\) tới \(V\). Nếu \(V\) không thể đi tới được từ \(U\), in ra -1.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên đại diện cho mảng \(next\) (\(0 \le next[i] < N\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(U\) và \(V\) (\(0 \le U, V < N\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra số bước đi ít nhất hoặc -1 trên một dòng.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, Q \le 1000\).
• Subtask 2 (70% số điểm): \(N, Q \le 10^5\).

Ví dụ

Input:

6 4
1 2 3 1 5 4
0 3
3 0
4 5
5 0

Output:

3
-1
1
-1

Giải thích:

• Cung đồ thị: \(0 \to 1 \to 2 \to 3 \to 1\) và \(4 \to 5 \to 4\).
• Truy vấn 1 (\(0 \to 3\)): Đi qua \(0 \to 1 \to 2 \to 3\) (3 bước).
• Truy vấn 2 (\(3 \to 0\)): Không thể đi ngược từ chu kỳ về 0 \(\to\) -1.
• Truy vấn 3 (\(4 \to 5\)): Đi qua \(4 \to 5\) (1 bước).
• Truy vấn 4 (\(5 \to 0\)): Hai đỉnh nằm ở hai thành phần liên thông khác nhau \(\to\) -1.