공이 \(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\)개의 공이 각각 어느 상자에 들어 있는지 구하는 프로그램을 작성하라. |
입력은 다음 형식으로 주어진다.
\(N\) \(M\)
\(X_1\) \(Y_1\)
\(X_2\) \(Y_2\)
\(\vdots\)
\(X_M\) \(Y_M\)
- 첫째 줄에 정수 \(N\)과 \(M\)이 공백 하나로 구분되어 주어진다.
- 다음 \(M\)줄의 \(j\)번째 줄에 정수 \(X_j\)와 \(Y_j\)가 공백 하나로 구분되어 주어진다.
- \(1 \le N \le 2000\)
- \(1 \le M \le 2000\)
- \(1 \le X_j \le N\)
- \(1 \le Y_j \le N\)
- 입력되는 값은 모두 정수이다.
다음 형식으로 출력한다.
\(N\)줄을 출력한다. \(i\)번째 줄에는 \(M\)번 조작을 모두 끝낸 뒤 공 \(i\)가 들어 있는 상자의 번호를 출력한다.
처음에는 상자 \(1\)에 공 \(1\), 상자 \(2\)에 공 \(2\), 상자 \(3\)에 공 \(3\)이 들어 있다. \(1\)번째 조작에서 공 \(1\)을 상자 \(2\)로, \(2\)번째에서 공 \(3\)을 상자 \(2\)로, \(3\)번째에서 공 \(2\)를 상자 \(1\)로, \(4\)번째에서 공 \(1\)을 상자 \(3\)으로 옮긴다. 끝나면 공 \(1\)은 상자 \(3\), 공 \(2\)는 상자 \(1\), 공 \(3\)은 상자 \(2\)에 있다.