배달 경로의 바로 앞

문제

배달 앱은 한 배달원이 방문할 배달 지점의 순서를 관리한다. 배달 지점은 1번부터 N번까지 있으며, 처음에는 번호가 작은 지점부터 차례대로 방문하도록 되어 있다. 아직 배달을 시작하지 않은 상태에서 운영자가 방문 순서를 여러 번 수정한다. 지점은 수정 과정에서 추가되거나 사라지지 않으며, 모든 지점은 항상 방문 목록에 정확히 한 번씩 존재한다. 한 번의 수정 요청은 서로 다른 두 지점 번호 x와 y로 주어진다. 앱은 현재 목록에서 x를 꺼낸 다음, 현재 y가 있는 위치의 바로 앞에 x를 삽입한다. 여기서 번호는 지점의 고유 번호이며, 현재 목록에서의 순번을 뜻하지 않는다. x를 꺼낼 때 x를 제외한 지점들의 상대적인 순서는 그대로 유지한다. 이후 삽입할 때도 x를 제외한 지점들의 상대적인 순서는 바꾸지 않는다. 예를 들어 현재 순서가 3, 1, 4, 2이고 요청이 x=2, y=1이면, 2를 꺼낸 뒤 1의 바로 앞에 넣으므로 새 순서는 3, 2, 1, 4가 된다. x가 이미 y의 바로 앞에 있다면 목록은 변하지 않는다. y가 첫 번째 지점이라면 x는 새로운 첫 번째 지점이 된다. 마지막 지점을 꺼내거나 첫 번째 지점을 다른 곳으로 옮기는 요청도 같은 규칙으로 처리한다. 수정 요청은 주어진 순서대로 모두 반영한다. 앞선 요청으로 달라진 방문 순서가 다음 요청의 기준이 되며, 지점 번호가 작다는 이유로 자동 정렬하지 않는다. 요청마다 목록을 출력할 필요는 없다. 모든 수정이 끝난 뒤 배달 앱에 표시할 최종 방문 순서를 구해야 한다. 수정 요청이 하나도 없으면 처음의 방문 순서를 그대로 출력한다. 지점이 한 개뿐인 경우에는 서로 다른 두 지점을 고를 수 없으므로 수정 요청이 주어지지 않는다.

입력

첫째 줄에 지점 수 N과 수정 요청 수 Q가 주어진다. 다음 Q개 줄에 두 지점 번호 x와 y가 주어진다.
모든 입력값은 정수이다. 1≤N≤200,000, 0≤Q≤20,000, 1≤x,y≤N, x≠y이다. N=1이면 Q=0이다.

출력

모든 수정 요청을 처리한 뒤의 지점 번호 N개를 방문 순서대로 한 줄에 공백으로 구분하여 출력한다.

5 4
5 2
1 4
3 5
4 2

3 5 4 2 1

4 3
1 2
4 1
2 4

2 4 1 3

1 0

1

출처: Devin.KR 자체 제작