공의 이동
면접 대비시간 제한2초메모리 제한1024 MB
지정된 공을 지정된 상자로 옮기는 작업을 여러 번 수행한 뒤 각 공이 어느 상자에 있는지 구한다.
문제
N개의 공이 있고, 1부터 N까지 번호가 붙어 있다. 또 공을 몇 개든 넣을 수 있는 N개의 상자가 있고, 상자에도 1부터 N까지 번호가 붙어 있다.
상자 i (1 ≤ i ≤ N)에는 처음에 공 i가 들어 있었다.
JOI 고등학교 학생인 아오이는 이 상태에서 상자와 공에 대해 M번의 조작을 했다. j번째 (1 ≤ j ≤ M) 조작은 다음과 같이 이루어졌다.
- 공
Xj가 들어 있는 상자를 찾아, 그 상자에서 공Xj를 꺼낸다. 그 후 상자Yj에 공Xj를 넣는다.
아오이가 M번의 조작을 모두 마친 뒤, N개의 공이 각각 어느 상자에 들어 있는지 구하라.
입력
입력은 다음 형식으로 표준 입력에서 주어진다.
N M
X1 Y1
X2 Y2
:
XM YM
출력
N행으로 출력하라. i행째 (1 ≤ i ≤ N)에는 아오이가 M번의 조작을 모두 마친 뒤 공 i가 들어 있는 상자의 번호를 출력하라.
제한
1 ≤ N ≤ 2000.1 ≤ M ≤ 2000.1 ≤ Xj ≤ N(1 ≤ j ≤ M).1 ≤ Yj ≤ N(1 ≤ j ≤ M).- 입력되는 값은 모두 정수이다.