아이잔은 N개의 정수 S[0], S[1], ..., S[N-1]로 이루어진 수열 S를 가지고 있다. 수열은 0부터 N-1까지 서로 다른 N개의 정수로 이루어져있다. 아이잔은 두 수의 위치를 바꾸며 이 수열을 오름차순으로 정렬하려고 한다. 아이잔의 오랜 친구인 에르맥도 수열에서 두 수를 바꾸는데, 아이잔과는 다르게 정렬하려는 목적 없이 아무렇게나 바꾼다.

아이잔과 에르맥은 라운드를 거치며 수열을 조작한다. 각 라운드마다, 에르맥이 먼저 위치 바꾸기를 하고 그 다음 아이잔이 위치 바꾸기를 한다. 위치 바꾸기에 대해서 좀 더 자세히 말하자면, 바꿀 두 위치를 정하고 그 위치에 있는 값을 맞바꾼다. 이때 정하는 두 위치가 다를 필요는 없다. 만약 정한 두 위치가 같으면 수열에 아무런 변화가 없다.

아이잔은 에르맥이 수열 S를 정렬하려는 목적 없이 아무렇게나 바꾼다는 사실을 알고 있다. 더 나아가서 라운드를 시작하기 전부터 에르맥이 어떻게 위치 바꾸기를 할 건지 미리 다 알고 있다. 에르맥은 M 라운드에 대한 계획을 가지고 있다. 라운드의 번호를 순서대로 0 부터 M-1 까지 매겼을 때, i번 라운드에서 에르맥이 바꿀 두 위치는 X[i]와 Y[i]이다.

아이잔은 수열 S를 오름차순으로 정렬하길 원한다. 각 라운드를 시작하기 전에 만약 수열이 이미 정렬되어 있다면 라운드를 더 이상 진행하지 않고 멈출 수 있다. 처음 수열 S에 대한 정보와 에르맥이 M 라운드 동안 어떻게 위치 바꾸기를 할지에 대한 정보가 주어졌을 때, 아이잔이 어떻게 위치 바꾸기를 해야할지 구하시오. 언제나 M 라운드 안에 정렬이 가능하도록 입력이 주어진다.

만약 어떤 라운드에서 에르맥이 위치 바꾸기를 한 뒤 수열이 정렬되어 있다면, 아이잔은 같은 두 위치를 맞바꿔주면 된다 (예를 들어 0번 위치와 0번 위치). 그러면 이 라운드의 끝에서 수열 S는 정렬되고 아이잔은 멈출 수 있다. 또한 처음부터 수열 S가 정렬되어 있다면 필요한 라운드의 최소 수는 0 이다.

예제 1

• 처음 수열 S = 4, 3, 2, 1, 0
• 에르맥은 M = 6라운드를 진행하려 한다.
• 에르맥이 바꿀 위치에 대한 정보 X와 Y는 X = 0, 1, 2, 3, 0, 1이며, Y = 1, 2, 3, 4, 1, 2 이다. 다르게 얘기하면 에르맥은 (0, 1), (1,2), (2,3), (3,4), (0, 1) 그리고 (1, 2) 순서대로 위치를 바꿀 계획이다.

이러한 상황에서 아이잔은 3 라운드 만에 수열 S를 0, 1, 2, 3, 4로 정렬할 수 있다. 아이잔은 (0, 4), (1, 3) 그리고 (3, 4) 순서대로 위치 바꾸기를 하면 된다.

아래 표는 각 위치 바꾸기마다 수열 S의 내용이 어떻게 바뀌는지 나타내고 있다.

예제 2

• 처음 수열 S = 3, 0, 4, 2, 1
• 에르맥은 M = 5라운드를 진행하려 한다.
• 에르맥은 (1, 1), (4, 0), (2, 3), (1, 4) 그리고 (0, 4) 순서대로 위치를 바꿀 계획이다.

이러한 상황에서 아이잔은 3 라운드 만에 수열 S를 정렬할 수 있다. 아이잔은 (1, 4), (4, 2) 그리고 (2, 2) 순서대로 위치 바꾸기를 하면 된다.

아래 표는 각 위치 바꾸기마다 수열 S의 내용이 어떻게 바뀌는지 나타내고 있다.

수열 S와 정수 M, 그리고 X, Y가 주어진다.

아이잔이 수열 S를 정렬하기 위해 어떻게 위치를 바꿀지에 대해 계산하자.

다음 함수 findSwapPairs를 구현해야 한다.

• findSwapPairs(N, S, M, X, Y, P, Q) — 이 함수는 단 한 번 그레이더에 의해 호출된다.
  • N: 수열 S의 크기
  • S: 처음 수열 S에 대한 정보를 가지고 있는 정수 배열
  • M: 에르맥이 계획한 라운드 수
  • X, Y: 크기가 M인 정수 배열들. 0 ≤ i ≤ M-1 인 i에 대해 i번 라운드에서 에르맥은 두 위치 X[i], Y[i]에 있는 수를 맞바꾼다.
  • P, Q: 정수 배열들. 아이잔이 바꿀 위치에 대한 정보를 위해 필요한 배열이다. R이 여러분이 구한 정렬하기 위해 필요한 라운드 수라고 하자. 0과 R-1 사이의 i에 대해서 i번 라운드에 아이잔이 고른 맞바꿀 두 위치를 P[i]와 Q[i]에 저장한다. 배열 P와 Q는 이미 크기 M으로 메모리가 잡혀있다.
  • 이 함수는 위에 정의된 R 값을 리턴해야 한다.
  </ul> </li>

  M라운드 혹은 보다 더 일찍 정렬 가능하도록 입력이 주어진다.

  입력 형식

  • 1번 줄: N
  • 2번 줄: S[0] … S[N - 1]
  • 3번 줄: M
  • 4 ~ M + 3번 줄: X[i] Y[i]

  출력 형식

  findSwapPairs가 리턴한 값을 출력한다.

  다음 양식에 따라 출력한다:

  • 1번 줄: findSwapPairs의 리턴값 R
  • 2+i번 줄 (0 ≤ i < R): P[i] Q[i]

  예제 입력

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

  예제 출력

  3
  0 4
  1 3
  3 4