아이잔은 N개의 정수 S₀, S₁, ... , S_N-1로 이루어진 수열 S를 가지고 있다.

수열은 0부터 N - 1까지 서로 다른 N개의 정수로 이루어져있다.

아이잔은 두 수의 위치를 바꾸며 이 수열을 오름차순으로 정렬하려고 한다.

아이잔의 오랜 친구인 에르맥도 수열에서 두 수를 바꾸는데, 아이잔과는 다르게 정렬하려는 목적 없이 아무렇게나 바꾼다.

아이잔과 에르맥은 라운드를 거치며 수열을 조작한다.

각 라운드마다, 에르맥이 먼저 위치 바꾸기를 하고 그 다음 아이잔이 위치 바꾸기를 한다.

위치 바꾸기에 대해서 좀 더 자세히 말하자면, 바꿀 두 위치를 정하고 그 위치에 있는 값을 맞바꾼다.

이 때 정하는 두 위치가 다를 필요는 없다.

만약 정한 두 위치가 같으면 수열에 아무런 변화가 없다.

아이잔은 에르맥이 수열 S를 정렬하려는 목적 없이 아무렇게나 바꾼다는 사실을 알고 있다.

더 나아가서 라운드를 시작하기 전부터 에르맥이 어떻게 위치 바꾸기를 할 건지 미리 다 알고 있다.

에르맥은 M 라운드에 대한 계획을 가지고 있다.

라운드의 번호를 순서대로 0부터 M - 1까지 매겼을 때, i번 라운드에서 에르맥이 바꿀 두 위치는 X_i와 Y_i이다.

아이잔은 수열 S를 최대한 빠르게 오름차순으로 정렬하길 원한다.

각 라운드를 시작하기 전에 만약 수열이 이미 정렬되어 있다면 라운드를 더 이상 진행하지 않고 멈출 수 있다.

처음 수열 S에 대한 정보와 에르맥이 M 라운드 동안 어떻게 위치 바꾸기를 할지에 대한 정보가 주어졌을 때, 아이잔이 어떻게 위치 바꾸기를 해야할지 구하시오.

아이잔은 가능한 가장 적은 라운드만에 정렬을 해야한다.

또한, 언제나 라운드 안에 정렬이 가능하도록 입력이 주어진다.

Sorting timer 1초 memory 512MB

Sorting 1초 512MB