페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5853

공 옮겨담기 (Moving Balls) 2초 1024MB

문제

1...N으로 번호가 붙은 공 N개와 마찬가지로 1...N으로 번호가 붙은 바구니 N개가 있다.

각 공은 자신의 번호와 동일한 바구니에 들어가 있는데, 우리는 M번의 조작을 통해 공들의 위치를 바꿔보려고 한다.

각 조작은 X Y로 주어지는데, 이는 X번 공이 들어있는 바구니를 찾아 해당 바구니에서 공을 꺼내 Y번 바구니로 옮기는 것이다.

총 M번의 조작이 끝난 후 각 공들의 위치를 출력하는 프로그램을 작성하자.


입력

아래와 같은 형식의 입력이 주어진다.

N M

X_1 Y_1

X_2 Y_2

.

.

X_M Y_M

[제한]

1 ≦ N ≦ 2000

1 ≦ M ≦ 2000

1 ≦ X_i ≦ N (1 ≦ i ≦ M)

1 ≦ Y_i ≦ N (1 ≦ i ≦ M)


출력

총 M번의 조작이 끝난 후 각 공들의 위치를 출력한다.


예제1

입력
34
12
32
21
13
출력
3
1
2

처음에는 상자 1에는 공 1이, 상자 2에는 공 2가, 상자 3에는 공 3이 들어 있었다.

다음과 같이 4회의 조작을 행하였다.

  • 첫 번째 조작에서는 볼 1을 상자 1에서 꺼낸 다음 상자 2에 넣는다.

  • 두 번째 조작에서는 볼 3을 상자 3에서 꺼낸 다음 상자 2에 넣는다.

  • 세 번째 조작에서는 볼 2를 상자 2에서 꺼낸 다음 상자 1에 넣는다.

  • 네 번째 조작에서는 볼 1을 상자 2에서 꺼낸 다음 상자 3에 넣는다.

모든 작업이 끝나면 볼 1은 상자 3, 볼 2는 상자 1, 볼 3은 상자 2에 있다. 따라서 3,1,2는이 순서로 개행 구분 기호로 출력된다.


예제2

입력
33
11
22
33
출력
1
2
3

예제3

입력
42
13
24
출력
3
4
3
4

예제4

입력
48
13
32
24
23
41
21
14
33
출력
4
1
3
1

출처

JOI 2022 예선

역링크