Có \(N\) quả bóng, được đánh số từ \(1\) đến \(N\), và \(N\) chiếc hộp, cũng được đánh số từ \(1\) đến \(N\). Mỗi hộp có thể chứa bao nhiêu quả bóng cũng được. 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 với các hộp và bóng. Trong thao tác thứ \(j\) (\(1 \le j \le M\)), Aoi tìm hộp đang chứa quả bóng \(X_j\), lấy quả bóng \(X_j\) ra khỏi hộp đó, rồi đặt quả bóng này vào hộp \(Y_j\).

Hãy xác định từng quả bóng trong \(N\) quả bóng nằm trong hộp nào sau khi Aoi hoàn thành cả \(M\) thao tác.

Dữ liệu vào

Dữ liệu vào có dạng:

N M
X_1 Y_1
X_2 Y_2
...
X_M Y_M

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(i\) (\(1 \le i \le N\)) chứa số của hộp đang chứa quả bóng \(i\) sau khi Aoi hoàn thành cả \(M\) thao tác.

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ị trong dữ liệu vào đều là số nguyên.

Ví dụ

3 4
1 2
3 2
2 1
1 3

3
1
2

3 3
1 1
2 2
3 3

1
2
3

4 2
1 3
2 4

3
4
3
4

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

4
1
3
1

Nguồn

Đề bài Moving Balls, JOI 2021/2022, vòng loại thứ nhất, đợt 3, bài 4 của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.