Problem Description

There is a rooted tree with $ N $ vertices, numbered from $ 1 $ to $ N $. Each vertex, except for the root, has a single directed edge pointing from its parent to itself. Note that the root is not necessarily vertex $ 1 $.

Takahashi added $ M $ new directed edges to this graph. Each added edge $u \rightarrow v$ extends from some vertex $ u $ to a descendant vertex $ v $.

You are given a directed graph with $ N $ vertices and $ N-1+M $ edges after Takahashi added the edges. More specifically, $ N-1+M $ pairs of integers $ (A_1, B_1), ..., (A_{N-1+M}, B_{N-1+M}) $ are given, indicating that the $ i $-th edge extends from vertex $ A_i $ to vertex $ B_i $.

Restore the original rooted tree.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ B_1 $ $ : $ $ A_{N-1+M} $ $ B_{N-1+M} $

Output Format

Output $ N $ lines. On the $ i $-th line, output 0 if vertex $ i $ is the root of the original tree; otherwise, output the integer representing the parent of vertex $ i $ in the original tree.

It can be shown that the original tree is uniquely determined.

Sample Input and Output

Sample Input #1

3 1
1 2
1 3
2 3

Sample Output #1

0
1
2

Sample Input #2

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

Sample Output #2

6
4
2
0
6
2

Notes/Hints

Notes

For terms related to "trees" and other graph theory terminology, please refer to articles on Wikipedia.

Constraints

• $3 \leq N$
• $1 \leq M$
• $N + M \leq 10^5$
• $1 \leq A_i, B_i \leq N$
• $A_i \neq B_i$
• $(A_i, B_i) \neq (A_j, B_j)$ for $i \neq j$
• The input graph can be obtained by adding $ M $ edges to a rooted tree of $ N $ vertices satisfying the conditions described in the problem.

见题面 Input 部分

见题面 Output 部分