תיאור הבעיה

ישנם $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