Cho một tập bài gồm 𝑛 lá bài đánh số từ 1 tới 𝑛 theo thứ tự từ trên xuống dưới. Đầu tiên người ta viết vào mỗi lá bài một số nguyên là số thứ tự lá bài đó. Xét phép tráo 𝑆(𝑖,𝑗): Rút ra lá bài ghi số nguyên 𝑖 và chèn lên trên lá bài mang số nguyên 𝑗 (𝑖≠𝑗).

Ví dụ: Với 𝑛=9

Cho 𝑥 phép tráo bài, hãy xác định trạng thái của tập bài sau 𝑥 phép tráo.

Dữ liệu: Vào từ file văn bản SHUFFLE.INP

• Dòng 1 chứa hai số nguyên dương 𝑛, 𝑥 ≤ 10⁵
• 𝑥 dòng tiếp theo, dòng thứ 𝑘 chứa hai số nguyên dương 𝑖_𝑘, 𝑗_𝑘 cho biết phép tráo thứ 𝑘 là 𝑆(𝑖_𝑘,𝑗_𝑘) (𝑖_𝑘≠𝑗_𝑘,1 ≤ 𝑖_𝑘, 𝑗_𝑘 ≤ 𝑛)

Kết quả: Ghi ra file văn bản SHUFFLE.OUT một dòng gồm 𝑛 số nguyên là các số ghi trên các lá bài theo thứ tự từ trên xuống dưới

Các số trên một dòng của Input/Output files được/phải ghi cách nhau ít nhất một dấu cách

Ví dụ