Alice tạo một hoán vị ~P~ là hoán vị của các số ~0, 1, \dots, n - 1~. Các phần tử của hoán vị được đánh chỉ số từ ~0~ đến ~n - 1~. Alice định nghĩa một vòng trên hoán vị ~P~ là một dãy các chỉ số ~(i_1, i_2, \dots, i_k)~ sao cho: ~P(i_1) = i_2; P(i_2) = i_3; \dots; P(i_{k-1}) = i_k; P(i_k) = i_1~.

Ví dụ, trên hoán vị ~(2, 0, 1, 5, 4, 3)~ có ba vòng ~(0, 2, 1), (3, 5), (4)~.

Tiếp theo, Alice tạo ra ~m~ kịch bản độc lập trên hoán vị ~P~, kịch bản thứ ~t~ (~1 \le t \le m~) sẽ tráo đổi hai phần tử ở vị trí ~x_t, y_t~ (~0 \le x_t < y_t \le n - 1~) cho nhau và đố Bob biết trên hoán vị ~P~ sau khi tráo đổi có bao nhiêu vòng.

Yêu cầu: Cho hoán vị ~P~ và ~m~ kịch bản độc lập, với mỗi kịch bản hãy giúp Bob đếm số vòng trên hoán vị sau khi tráo đổi.

Input

• Dòng đầu chứa hai số nguyên dương ~n, m~ (~n, m \le 3 \times 10^5~);
• Dòng thứ hai chứa ~n~ số nguyên ~P(0), P(1), \dots, P(n - 1)~ mô tả hoán vị ~P~ ban đầu;
• Dòng thứ ~t~ (~1 \le t \le m~) trong ~m~ dòng tiếp theo chứa hai số ~x_t, y_t~ (~0 \le x_t < y_t \le n - 1~).

Output

• Ghi ra ~m~ dòng, mỗi dòng chứa một số là số vòng trong hoán vị sau khi tráo đổi tương ứng với từng kịch bản.

Subtasks

• Có ~20%~ số test thỏa mãn: ~n \le 3~;
• ~40%~ số test khác thỏa mãn: ~n, m \le 3000~;
• ~40%~ số test còn lại không có ràng buộc nào thêm.

Sample Input 1

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

Sample Output 1

1
3
3