Условие задачи

Имеется $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