공의 이동

문제

$N$ 개의 공이 있으며, $1$ 부터 $N$ 까지의 번호가 붙어 있다. 또한 공을 몇 개든 넣을 수 있는 $N$ 개의 상자가 있으며, 상자에는 $1$ 부터 $N$ 까지의 번호가 붙어 있다.

상자 $i$ ($1 \le i \le N$) 에는 처음에 공 $i$ 가 들어 있었다.

JOI 고등학교의 학생인 아오이는 이 상태에서 상자와 공에 대해 $M$ 번의 조작을 했다. $j$ 번째 ($1 \le j \le M$) 조작은 다음과 같이 이루어졌다.

• 공 $X_{j}$ 가 들어 있는 상자를 찾아, 그 상자에서 공 $X_{j}$ 를 꺼낸다. 그 후, 상자 $Y_{j}$ 에 공 $X_{j}$ 를 넣는다.

아오이가 $M$ 번의 조작을 모두 마친 후, $N$ 개의 공이 각각 어느 상자에 들어 있는지를 구하는 프로그램을 작성하시오.

제한

• $1 \le N \le 2000$.
• $1 \le M \le 2000$.
• $1 \le X_{j} \le N$ ($1 \le j \le M$).
• $1 \le Y_{j} \le N$ ($1 \le j \le M$).
• 입력되는 값은 모두 정수이다.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.
$N$ $M$
$X_{1}$ $Y_{1}$
$X_{2}$ $Y_{2}$
$:$
$X_{M}$ $Y_{M}$

출력

$N$ 줄에 걸쳐 출력한다. $i$ 번째 줄 ($1 \le i \le N$) 에는, 아오이가 $M$ 번의 조작을 모두 마친 후 공 $i$ 가 들어 있는 상자의 번호를 출력한다.

예제 입력 1

3 4
1 2
3 2
2 1
1 3

예제 출력 1

3
1
2

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

아오이는 다음과 같이 $4$ 번의 조작을 했다.

• $1$ 번째 조작에서는 공 $1$ 을 상자 $1$ 에서 꺼낸 후, 상자 $2$ 에 넣었다.
• $2$ 번째 조작에서는 공 $3$ 을 상자 $3$ 에서 꺼낸 후, 상자 $2$ 에 넣었다.
• $3$ 번째 조작에서는 공 $2$ 를 상자 $2$ 에서 꺼낸 후, 상자 $1$ 에 넣었다.
• $4$ 번째 조작에서는 공 $1$ 을 상자 $2$ 에서 꺼낸 후, 상자 $3$ 에 넣었다.

조작을 모두 마친 후, 공 $1$ 은 상자 $3$ , 공 $2$ 는 상자 $1$ , 공 $3$ 은 상자 $2$ 에 들어 있다. 따라서 $3,1,2$ 를 이 순서대로 줄바꿈으로 구분하여 출력한다.

예제 입력 2

3 3
1 1
2 2
3 3

예제 출력 2

1
2
3

조작을 모두 마친 후, 공 $1$ 은 상자 $1$ , 공 $2$ 는 상자 $2$ , 공 $3$ 은 상자 $3$ 에 들어 있다. 따라서 $1,2,3$ 을 이 순서대로 줄바꿈으로 구분하여 출력한다.

예제 입력 3

4 2
1 3
2 4

예제 출력 3

3
4
3
4

예제 입력 4

4 8
1 3
3 2
2 4
2 3
4 1
2 1
1 4
3 3

예제 출력 4

4
1
3
1