وصف المسألة

توجد $N$ من الكرات، مرقمة من $1$ إلى $N$. وتوجد أيضاً $N$ من الصناديق يمكن وضع أي عدد من الكرات فيها، وهذه الصناديق مرقمة من $1$ إلى $N$.

في البداية، كان الصندوق $i$ ($1 \le i \le N$) يحتوي على الكرة $i$.

قامت آوي، وهي طالبة في مدرسة JOI الثانوية، بإجراء $M$ من العمليات على الصناديق والكرات انطلاقاً من هذه الحالة. تمت العملية رقم $j$ ($1 \le j \le M$) على النحو التالي:

• ابحث عن الصندوق الذي يحتوي على الكرة $X_j$، وأخرج الكرة $X_j$ من ذلك الصندوق. بعد ذلك، ضع الكرة $X_j$ في الصندوق $Y_j$.

بعد أن تنهي آوي جميع العمليات الـ $M$، أوجد في أي صندوق توجد كل كرة من الكرات الـ $N$.

القيود

• $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$).
• جميع القيم المدخلة هي أعداد صحيحة.

الإدخال

يُعطى الإدخال من الدخل القياسي بالصيغة التالية:

N M
X_1 Y_1
X_2 Y_2
:
X_M Y_M

الإخراج

اطبع $N$ من الأسطر. في السطر رقم $i$ ($1 \le i \le N$)، اطبع رقم الصندوق الذي يحتوي على الكرة $i$ بعد أن تنهي آوي جميع العمليات الـ $M$.

أمثلة الإدخال والإخراج

مثال الإدخال 1

3 4
1 2
3 2
2 1
1 3

مثال الإخراج 1

3
1
2

في البداية، كان الصندوق $1$ يحتوي على الكرة $1$، والصندوق $2$ يحتوي على الكرة $2$، والصندوق $3$ يحتوي على الكرة $3$.

قامت آوي بإجراء $4$ عمليات كما يلي:

• في العملية $1$، أخرجت الكرة $1$ من الصندوق $1$ ثم وضعتها في الصندوق $2$.
• في العملية $2$، أخرجت الكرة $3$ من الصندوق $3$ ثم وضعتها في الصندوق $2$.
• في العملية $3$، أخرجت الكرة $2$ من الصندوق $2$ ثم وضعتها في الصندوق $1$.
• في العملية $4$، أخرجت الكرة $1$ من الصندوق $2$ ثم وضعتها في الصندوق $3$.

بعد الانتهاء من جميع العمليات، توجد الكرة $1$ في الصندوق $3$، والكرة $2$ في الصندوق $1$، والكرة $3$ في الصندوق $2$. لذلك نطبع $3, 1, 2$ بهذا الترتيب، مفصولة بأسطر جديدة.

مثال الإدخال 2

3 3
1 1
2 2
3 3

مثال الإخراج 2

1
2
3

بعد الانتهاء من جميع العمليات، توجد الكرة $1$ في الصندوق $1$، والكرة $2$ في الصندوق $2$، والكرة $3$ في الصندوق $3$. لذلك نطبع $1, 2, 3$ بهذا الترتيب، مفصولة بأسطر جديدة.

مثال الإدخال 3

4 2
1 3
2 4

مثال الإخراج 3

3
4
3
4

مثال الإدخال 4

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

مثال الإخراج 4

4
1
3
1