{"code":"shuffle","name":"Tráo bài","description":"Cho một tập bài gồm $n$ 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á\r\nbà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\r\nmang số nguyên $𝑗 (𝑖 \\neq 𝑗)$.\r\n*Ví dụ*: Với $𝑛 = 9$\r\n\r\n$(1,2,3,4,5,6,7,8,9) \\xrightarrow[]{S(2,8)} (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))$\r\n\r\n**Yêu cầu:** 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.\r\n\r\n#### Input\r\n- Dòng 1 chứa hai số nguyên dương $𝑛, 𝑥 \\leq 10^5$\r\n- $𝑥$ 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à $𝑆(𝑖_𝑘,𝑗_𝑘) (𝑖_𝑘 \\neq 𝑗_𝑘, 1 \\leq 𝑖_𝑘,𝑗_𝑘 \\leq 𝑛)$\r\n\r\n#### Output \r\n- Ghi ra 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\r\n\r\n*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*\r\n\r\n#### Scoring \r\n- Subtask $1$ ($32.5\\%$ số điểm): $𝑛, 𝑥 \\leq 10^3$\r\n- Subtask $2$ ($67.5\\%$ số điểm): $𝑛, 𝑥 \\leq 10^5$\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        9 3\r\n        8 2\r\n        4 7\r\n        1 9 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        8 2 3 5 6 4 7 1 9\r\n        ```","points":200.0,"partial":true,"time_limit":1.0,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}