Problem Statement

There are N delinquent monkeys on this island.

Each monkey has a rank from 1 to N: the monkey of rank 1 is numbered 1, the monkey of rank i is numbered i, and the lowest-ranked monkey, of rank N, is numbered N. No two monkeys have the same rank. After humans taught the monkeys the concept of organizations, organizational conflicts among the monkeys began on the island.

Initially, each monkey is independent, is its own boss, and forms a team with one member. When two monkeys from different teams fight, the bosses of the two teams face off, each bringing along all of its subordinates. The team with more members wins. If the teams have the same number of members, the boss with the higher rank (rank 1 or closer to rank 1) wins. The losing team is absorbed into the winning team. The boss of the winning team remains the boss. When monkeys of the same team fight, nothing happens, because the boss either mediates or wins. Data on the fights is given. After all fights have ended, report the boss of every monkey, in order from number 1 to N. If a monkey is its own boss, return its own number.

Input

$N$ $M$
$A1$ $B1$
$\dots$
$AM$ $BM$

N is the number of monkeys.
2 <= N<=10000
The monkeys are numbered; monkey number 1 has rank 1, and monkey number i has rank i. Therefore, no data on the monkeys' ranks is given.

M is the number of fights.
1 <= M<=N
1 <= Ai,Bi <= N
Ai Bi is data saying that monkeys Ai and Bi fought; both Ai and Bi are monkey numbers and are numeric. The fights are given in the order they occurred. Ai and Bi are not the same.

Output

$U1$
$\dots$
$UN$

For the monkeys numbered 1 to N, output the boss of each monkey in order, one per line. The output number Ui must be the boss of monkey number i.

Sample

6 6
2 1
1 4
3 5
5 6
3 6
3 4

1
1
1
1
1
1

11 8
1 4
2 3
4 3
5 9
6 8
8 10
8 11
5 10

1
1
1
1
6
6
7
6
6
6
6