정렬하기 2

아이잔은 0부터 $N-1$까지의 정수가 한 번씩 나오는 길이 $N$의 수열 $S$를 가지고 있다. 아이잔은 두 위치의 값을 맞바꾸는 방법으로 이 수열을 오름차순으로 정렬하려 한다.

아이잔의 오랜 친구 에르맥도 같은 수열에서 두 위치의 값을 맞바꾼다. 다만 에르맥은 정렬할 생각 없이 아무 위치나 고른다.

두 사람은 라운드를 반복한다. 한 라운드에서는 에르맥이 먼저 맞바꾸고, 이어서 아이잔이 맞바꾼다. 맞바꾸기는 위치 두 개를 고른 다음 그 두 위치의 값을 서로 바꾸는 것이다. 고른 두 위치가 같아도 되며, 그때는 수열이 그대로 남는다.

에르맥의 계획은 첫 라운드가 시작되기 전에 이미 아이잔에게 전부 알려져 있다. 계획은 $M$개의 라운드로 이루어지고 라운드 번호는 0부터 $M-1$까지다. $i$번 라운드에서 에르맥은 위치 $X[i]$와 $Y[i]$의 값을 맞바꾼다.

아이잔은 라운드를 시작하기 전에 수열이 오름차순으로 정렬되어 있으면 그 자리에서 멈춘다. 이때까지 진행한 라운드 수를 $R$이라 하자. 처음부터 정렬되어 있으면 $R = 0$이다. 어떤 라운드에서 에르맥이 맞바꾼 뒤 수열이 정렬되어 있으면, 아이잔은 같은 위치 두 개를 고르면 된다. 그러면 그 라운드가 끝난 시점에 수열은 정렬되어 있다.

수열 $S$와 에르맥의 계획 $M$, $X$, $Y$가 주어진다. $R$이 가장 작아지도록 아이잔이 라운드마다 고를 두 위치를 구하시오.

첫째 줄에 수열의 길이 $N$이 주어진다.

둘째 줄에 $S[0]$부터 $S[N-1]$까지 공백을 사이에 두고 주어진다.

셋째 줄에 에르맥이 계획한 라운드 수 $M$이 주어진다.

다음 $M$개의 줄 가운데 $i$번째 줄에는 $X[i]$와 $Y[i]$가 공백을 사이에 두고 주어진다.

• $1 \le N \le 500$
• $S$에는 0부터 $N-1$까지의 정수가 한 번씩 들어 있다
• $1 \le M \le 1000$
• $0 \le X[i], Y[i] \le N-1$
• 아이잔은 항상 $M$라운드 안에 수열을 정렬할 수 있다

첫째 줄에 가능한 가장 작은 라운드 수 $R$을 출력한다.

이어지는 $R$개의 줄에 아이잔이 고르는 위치를 출력한다. $i$번째 줄에는 $i$번 라운드에서 아이잔이 고른 두 위치 $P[i]$와 $Q[i]$를 $0 \le P[i] \le Q[i] \le N-1$이 되도록 공백을 사이에 두고 출력한다. $P[i] = Q[i]$는 수열을 그대로 두는 맞바꾸기를 뜻한다.

$R$이 최소인 답이 여러 가지면, $P[0], Q[0], P[1], Q[1], \dots, P[R-1], Q[R-1]$을 이 순서로 늘어놓은 수열이 사전순으로 가장 앞서는 답을 출력한다.

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