Mô tả bài toán

Có $N$ quả bóng, được đánh số từ $1$ đến $N$. Ngoài ra, có $N$ chiếc hộp có thể chứa bao nhiêu quả bóng tùy ý, và các hộp cũng được đánh số từ $1$ đến $N$.

Ban đầu, hộp $i$ ($1 \le i \le N$) chứa quả bóng $i$.

Aoi, một học sinh của trường trung học JOI, đã thực hiện $M$ thao tác trên các hộp và các quả bóng từ trạng thái này. Thao tác thứ $j$ ($1 \le j \le M$) được thực hiện như sau:

• Tìm chiếc hộp đang chứa quả bóng $X_j$ và lấy quả bóng $X_j$ ra khỏi hộp đó. Sau đó, bỏ quả bóng $X_j$ vào hộp $Y_j$.

Sau khi Aoi hoàn thành tất cả $M$ thao tác, hãy tìm xem mỗi quả bóng trong số $N$ quả bóng đang nằm ở hộp nào.

Ràng buộc

• $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$).
• Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu vào

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

N M
X_1 Y_1
X_2 Y_2
:
X_M Y_M

Kết quả

In ra $N$ dòng. Trên dòng thứ $i$ ($1 \le i \le N$), in ra số hiệu của chiếc hộp chứa quả bóng $i$ sau khi Aoi hoàn thành tất cả $M$ thao tác.

Ví dụ

Ví dụ 1 - Dữ liệu vào

3 4
1 2
3 2
2 1
1 3

Ví dụ 1 - Kết quả

3
1
2

Ban đầu, hộp $1$ chứa quả bóng $1$, hộp $2$ chứa quả bóng $2$, và hộp $3$ chứa quả bóng $3$.

Aoi đã thực hiện $4$ thao tác như sau:

• Ở thao tác thứ $1$, lấy quả bóng $1$ ra khỏi hộp $1$ rồi bỏ vào hộp $2$.
• Ở thao tác thứ $2$, lấy quả bóng $3$ ra khỏi hộp $3$ rồi bỏ vào hộp $2$.
• Ở thao tác thứ $3$, lấy quả bóng $2$ ra khỏi hộp $2$ rồi bỏ vào hộp $1$.
• Ở thao tác thứ $4$, lấy quả bóng $1$ ra khỏi hộp $2$ rồi bỏ vào hộp $3$.

Sau khi hoàn thành tất cả các thao tác, quả bóng $1$ ở trong hộp $3$, quả bóng $2$ ở trong hộp $1$, và quả bóng $3$ ở trong hộp $2$. Do đó, in ra $3, 1, 2$ theo thứ tự này, phân cách bởi dấu xuống dòng.

Ví dụ 2 - Dữ liệu vào

3 3
1 1
2 2
3 3

Ví dụ 2 - Kết quả

1
2
3

Sau khi hoàn thành tất cả các thao tác, quả bóng $1$ ở trong hộp $1$, quả bóng $2$ ở trong hộp $2$, và quả bóng $3$ ở trong hộp $3$. Do đó, in ra $1, 2, 3$ theo thứ tự này, phân cách bởi dấu xuống dòng.

Ví dụ 3 - Dữ liệu vào

4 2
1 3
2 4

Ví dụ 3 - Kết quả

3
4
3
4

Ví dụ 4 - Dữ liệu vào

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

Ví dụ 4 - Kết quả

4
1
3
1