연결 리스트

연결 리스트는 대학의 자료 구조 수업에서 흔히 배우는 기본적인 선형 자료 구조 중 하나다. 실제 응용에서의 실용성(혹은 비실용성)과는 별개로, 데이터를 연속하지 않은 저장 공간에 저장하는 방법을 보여 주는 데 자주 쓰인다.

연결 리스트의 세 가지 흔한 연산은 삽입, 삭제, 탐색이다. 이 문제에서는 실제 응용에서도 쓸모가 있을 법한 네 번째 연산인 슬라이딩을 다룬다. 1부터 N까지 순서대로 연결된 N개의 정수로 이루어진 연결 리스트가 주어진다고 하자 (1 → 2 → 3 → ... → N). 슬라이드 연산은 두 정수 a와 b를 받아, 즉 slide(a, b)로 주어지며, 정수 a를 자기 위치에서 b의 위치 바로 오른쪽으로 옮긴다.

예를 들어 N = 5라면 처음 연결 리스트는 1 → 2 → 3 → 4 → 5이다. 연산 slide(4, 1)을 수행하면 연결 리스트는 1 → 4 → 2 → 3 → 5가 된다. 즉 4가 자기 위치에서 1의 위치 바로 오른쪽으로 옮겨진다. 이때 4는 왼쪽으로 두 칸 이동한다. 이어서 slide(1, 5)를 수행하면 연결 리스트는 4 → 2 → 3 → 5 → 1이 된다. 즉 1이 자기 위치에서 5의 위치 바로 오른쪽으로 옮겨진다. 이때 1은 오른쪽으로 네 칸 이동한다.

1부터 N까지의 정수 N개가 순서대로 연결된 연결 리스트와 Q개의 슬라이드 연산이 주어진다. 각 slide(a, b) 연산마다 슬라이딩을 수행하고, a가 연결 리스트에서 몇 칸 이동했는지 출력한다. a가 왼쪽으로 이동했다면 음수로 출력하고(위 예에서의 −2처럼), 그렇지 않다면 음이 아닌 값으로 출력한다(위 예에서의 4처럼).

모든 연산을 수행한 뒤에는 최종 연결 리스트도 출력해야 한다.

입력의 첫 줄에는 두 정수 N Q (1 ≤ N, Q ≤ 100000)가 주어진다. 각각 연결 리스트에 있는 정수의 개수와 연산의 개수다. 다음 Q개의 줄에는 각각 두 정수 a b (1 ≤ a, b ≤ N; a ≠ b)가 주어지며, 수행할 slide(a, b) 연산을 나타낸다.

각 연산마다 해당 정수가 몇 칸 이동했는지 한 줄에 출력한다. 해당 정수가 왼쪽으로 이동했다면 음수를, 그렇지 않다면 음이 아닌 값을 출력한다. 마지막 줄에는 모든 연산을 수행한 뒤의 연결 리스트 데이터를 나타내는 N개의 정수를 공백 하나로 구분해 출력한다.