Умова задачі

Є $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$.

Визначте, у якій коробці перебуває кожен із $N$ м'ячів після того, як Аой завершить усі $M$ операцій.

Обмеження

• $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