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á
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 \(𝑗 (𝑖 \neq 𝑗)\).
Ví dụ: Với \(𝑛 = 9\)

\((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))\)

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.

Input

• Dòng 1 chứa hai số nguyên dương \(𝑛, 𝑥 \leq 10^5\)
• \(𝑥\) 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 𝑛)\)

Output

• 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

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

Scoring

• Subtask \(1\) (\(32.5\%\) số điểm): \(𝑛, 𝑥 \leq 10^3\)
• Subtask \(2\) (\(67.5\%\) số điểm): \(𝑛, 𝑥 \leq 10^5\)

Example

9 3
8 2
4 7
1 9 

8 2 3 5 6 4 7 1 9