Opis zadania

Mamy $N$ piłek ponumerowanych od $1$ do $N$. Mamy również $N$ pudełek, z których każde może pomieścić dowolną liczbę piłek; pudełka są ponumerowane od $1$ do $N$.

Początkowo w pudełku $i$ ($1 \le i \le N$) znajdowała się piłka $i$.

Aoi, uczennica liceum JOI, wykonała od tego stanu $M$ operacji na pudełkach i piłkach. $j$-ta operacja ($1 \le j \le M$) przebiegała następująco:

• Znajdź pudełko, w którym znajduje się piłka $X_j$, i wyjmij z niego piłkę $X_j$. Następnie włóż piłkę $X_j$ do pudełka $Y_j$.

Po wykonaniu przez Aoi wszystkich $M$ operacji wyznacz, w którym pudełku znajduje się każda z $N$ piłek.

Ograniczenia

• $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$).
• Wszystkie wartości wejściowe są liczbami całkowitymi.

Wejście

Wejście podawane jest ze standardowego wejścia w następującym formacie:

N M
X_1 Y_1
X_2 Y_2
:
X_M Y_M

Wyjście

Wypisz $N$ wierszy. W $i$-tym wierszu ($1 \le i \le N$) wypisz numer pudełka, w którym znajduje się piłka $i$ po wykonaniu przez Aoi wszystkich $M$ operacji.

Przykłady

Przykład wejścia 1

3 4
1 2
3 2
2 1
1 3

Przykład wyjścia 1

3
1
2

Początkowo w pudełku $1$ była piłka $1$, w pudełku $2$ była piłka $2$, a w pudełku $3$ była piłka $3$.

Aoi wykonała $4$ operacje w następujący sposób:

• W $1$. operacji wyjęła piłkę $1$ z pudełka $1$, a następnie włożyła ją do pudełka $2$.
• W $2$. operacji wyjęła piłkę $3$ z pudełka $3$, a następnie włożyła ją do pudełka $2$.
• W $3$. operacji wyjęła piłkę $2$ z pudełka $2$, a następnie włożyła ją do pudełka $1$.
• W $4$. operacji wyjęła piłkę $1$ z pudełka $2$, a następnie włożyła ją do pudełka $3$.

Po zakończeniu wszystkich operacji piłka $1$ znajduje się w pudełku $3$, piłka $2$ w pudełku $1$, a piłka $3$ w pudełku $2$. Wobec tego należy wypisać $3, 1, 2$ w tej kolejności, rozdzielając je znakami nowej linii.

Przykład wejścia 2

3 3
1 1
2 2
3 3

Przykład wyjścia 2

1
2
3

Po zakończeniu wszystkich operacji piłka $1$ znajduje się w pudełku $1$, piłka $2$ w pudełku $2$, a piłka $3$ w pudełku $3$. Wobec tego należy wypisać $1, 2, 3$ w tej kolejności, rozdzielając je znakami nowej linii.

Przykład wejścia 3

4 2
1 3
2 4

Przykład wyjścia 3

3
4
3
4

Przykład wejścia 4

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

Przykład wyjścia 4

4
1
3
1