Chọ dãy ~S~ gồm ~N~ số nguyên ~S[0], S[1], ..., S[N-1]~. Các số trong dãy ~S~ phân biệt, có giá trị từ ~0~ đến ~N-1~. Alice muốn sắp xếp dãy ~S~ theo thứ tự tăng dần bằng cách tráo đổi các cặp phần tử trong dãy ~S~. Bạn của cô ấy, Bob cũng giúp cô ấy sắp xếp dãy số ~S~. Alice và Bob sắp xếp dãy số qua một số vòng. Trong mỗi vòng, mỗi người đến lượt của mình sẽ chọn một cặp chỉ số hợp lệ ~(x,y)~ và tráo đổi hai phần tử ~S[x] ~ và ~S[y]~. Bob chọn trước, Alice chọn sau và hai chỉ số ~x, y ~ có thể trùng nhau. Alice biết chính xác các chỉ số ~(x,y)~ mà Bob sẽ chọn. Bob dự định giúp Alice sắp xếp dãy số trong ~M~ vòng, vòng thứ ~i~ ~(0 \leq i \leq M-1)~ sẽ chọn cặp chỉ số ~(X[i], Y[i])~. Khi sắp xếp dãy số, trước mỗi vòng, nếu Alice thấy dãy số đã được sắp tăng thì Alice kết thúc việc sắp xếp. Sau lượt của Bob, nếu dãy số đã được sắp tăng thì Alice có thể chọn hai chỉ số bằng nhau (trong trường hợp này, dãy số ~S~ sẽ không thay đổi) để hoàn thành trọn vẹn một vòng và quá trình sắp xếp cũng sẽ kết thúc. Nếu ban đầu dãy số S đã được sắp tăng thì số vòng Alice và Bob thực hiện sắp xếp dãy số là ~0~.

Yêu cầu

Tìm dãy chỉ số mà Alice đã chọn để sắp xếp dãy số S theo mô tả ở trên.

Dữ liệu vào

• Dòng ~1~: Số nguyên dương ~N~ - số phần tử của dãy số ~S~.
• Dòng ~2~: Dãy số ~S[0]...S[N-1]~.
• Dòng ~3~: Số nguyên dương ~M~ - số vòng hoán đổi theo dự định của Bob.
• Dòng ~4, ..., M+3~: Mỗi dòng chứa hai số ~X[i]~ và ~Y[i]~ - cặp chỉ số ở lượt chọn thứ ~i~ của Bob.

Kết quả ra

• Dòng ~1~: Số nguyên ~R~ - số vòng ít nhất mà Alice và Bob thực hiện sắp xếp dãy số ~S~.
• Dòng ~2+i~, ~(0 \leq i < R)~: Hai số nguyên ~P[i], Q[i]~ tương ứng là cặp chỉ số Alice chọn ở vòng thứ ~i~.

Sample input

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

Sample output

3
1 4
4 2
2 2

Subtasks

• Subtasks ~1~ (8% số điểm): ~1 \leq N \leq 5; M=N^2; X[i]=Y[i] = 0~ với mọi ~i; R \leq M;~
• Subtasks ~2~ (12% số điểm): ~1 \leq N \leq 100; M=30N; X[i]=Y[i] = 0~ với mọi ~i; R \leq M;~
• Subtasks ~3~ (16% số điểm): ~1 \leq N \leq 100; M=30N; X[i]=Y[i] = 1~ với mọi ~i; R \leq M;~
• Subtasks ~4~ (20% số điểm): ~1 \leq N \leq 500; M=30N; ~
• Subtasks ~5~ (20% số điểm): ~1 \leq N \leq 2000; M=3N; ~
• Subtasks ~6~ (24% số điểm): ~1 \leq N \leq 200000; M=3N; ~

Dữ liệu vào đảm bảo luôn tồn tại cách để Alice và Bob sắp xếp dãy số ~S~ không quá ~M~ vòng.