방해받으며 정렬하기

아이잔은 $0$부터 $N-1$까지의 정수가 한 번씩 나오는 길이 $N$의 수열 $S$를 가지고 있다. 아이잔은 두 위치의 값을 맞바꾸면서 이 수열을 오름차순으로 정렬하려고 한다. 아이잔의 오랜 친구 에르맥도 수열에서 두 위치를 맞바꾸는데, 아이잔과 달리 정렬하려는 목적 없이 아무렇게나 바꾼다.

두 사람은 라운드를 거치며 수열을 조작한다. 각 라운드에서 에르맥이 먼저 맞바꾸기를 하고, 그다음 아이잔이 맞바꾸기를 한다. 맞바꾸기는 위치 두 개를 고른 뒤 그 두 위치의 값을 교환하는 것이다. 고른 두 위치가 서로 같아도 되고, 이때 수열은 변하지 않는다.

아이잔은 에르맥이 아무렇게나 바꾼다는 사실을 알고 있고, 라운드가 시작하기 전부터 에르맥의 계획을 모두 알고 있다. 에르맥은 $M$개의 라운드를 계획했다. 라운드에 $0$번부터 $M-1$번까지 순서대로 번호를 붙이면, $i$번 라운드에서 에르맥이 맞바꾸는 두 위치는 $X[i]$와 $Y[i]$이다.

각 라운드를 시작하기 전에 수열이 이미 정렬되어 있으면 아이잔은 라운드를 더 진행하지 않고 멈출 수 있다. 어떤 라운드에서 에르맥이 맞바꾸기를 한 뒤 수열이 정렬되어 있다면, 아이잔은 같은 위치를 두 번 고르면 된다. 예를 들어 $0$번 위치와 $0$번 위치를 고르면 그 라운드가 끝날 때 수열은 정렬된 상태이고 아이잔은 멈출 수 있다. 처음부터 수열이 정렬되어 있다면 필요한 라운드 수는 $0$이다.

수열 $S$와 에르맥의 계획이 주어진다. 아이잔이 수열을 정렬하는 데 필요한 최소 라운드 수 $R$과 각 라운드에서 아이잔이 고를 두 위치를 구하시오. $M$ 라운드 안에 정렬할 수 있는 입력만 주어진다.

첫째 줄에 수열의 길이 $N$이 주어진다. ($1 \le N \le 200$)

둘째 줄에 $S[0], S[1], \ldots, S[N-1]$이 공백으로 구분되어 주어진다. 이 $N$개의 정수는 $0$부터 $N-1$까지의 값을 한 번씩 갖는다.

셋째 줄에 에르맥이 계획한 라운드 수 $M$이 주어진다. ($1 \le M \le 600$)

넷째 줄부터 $M$개의 줄 중 $i$번째 줄에는 $i$번 라운드에서 에르맥이 맞바꿀 두 위치 $X[i]$와 $Y[i]$가 공백으로 구분되어 주어진다. ($0 \le X[i], Y[i] \le N-1$)

$M$ 라운드 안에 수열을 정렬할 수 있는 입력만 주어진다.

첫째 줄에 아이잔이 수열을 정렬하는 데 필요한 최소 라운드 수 $R$을 출력한다.

이어지는 $R$개의 줄 중 $i$번째 줄에는 $i$번 라운드에서 아이잔이 고르는 두 위치 $P[i]$와 $Q[i]$를 공백으로 구분해 출력한다. $i$번 라운드에서는 에르맥이 $X[i]$와 $Y[i]$를 맞바꾼 뒤에 아이잔이 $P[i]$와 $Q[i]$를 맞바꾼다. 두 위치가 같아도 되며, 이때는 같은 수를 두 번 출력한다.

라운드 수가 $R$인 답이 여러 가지이면, 출력하는 수를 $P[0], Q[0], P[1], Q[1], \ldots, P[R-1], Q[R-1]$ 순서로 나열한 수열이 사전순으로 가장 앞서는 답 하나만 출력한다.

$R$이 $0$이면 첫째 줄만 출력한다.