TRÁO BÀI

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M

Nguồn bài:
LMH
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một tập bài gồm ~n~ lá bài đánh số từ ~1~ tới ~n~ 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ự của lá bài đó. Xét phép tráo ~S(i, j)~: rút ra lá bài ghi số nguyên ~i~ và chèn lên trên lá bài mang số nguyên ~j~ ~(i \ne j)~.

Ví dụ với ~n = 9~:

$$(1,2,3,4,5,6,7,8,9) \xrightarrow{S(8,2)} (1,8,2,3,4,5,6,7,9) \xrightarrow{S(4,7)} (1,8,2,3,5,6,4,7,9) \xrightarrow{S(1,9)} (8,2,3,5,6,4,7,1,9)$$

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

Input
  • Dòng đầu tiên chứa hai số nguyên dương ~n, x~ ~(n, x \le 10^5)~.
  • ~x~ dòng tiếp theo, dòng thứ ~k~ chứa hai số nguyên dương ~i_k, j_k~ cho biết phép tráo thứ ~k~ là ~S(i_k, j_k)~ ~(i_k \ne j_k; 1 \le i_k, j_k \le n)~.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output
  • In ra một dòng gồm ~n~ 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.
Sample Input
9 3
8 2
4 7
1 9
Sample Output
8 2 3 5 6 4 7 1 9

Đang tải...