Queries and Trees 2

Time limit3sMemory limit1024 MB

Summary

Given M pairs of vertices and the LCA of each pair in an unknown rooted tree (root 1), print the parent of every vertex.

Level: Medium7 of 10
Topics: Tree, Union-find, Graph
Solved: No attempts yet

Problem

A tree with N ( $1 \le N \le 100,000$ ) vertices is given. Each vertex is numbered from 1 to N, and vertex 1 is the root.

You, who like trees and queries, are given M ( $1 \le M \le 100,000$ ) pairs of vertices, along with the lowest common ancestor of each pair.

However, you do not actually know what the tree is.

Input

The first line contains two integers N and M.

The next M lines each contain u, v, and w, meaning the lowest common ancestor of vertices u and v is vertex w. ( $1 \le u, v, w \le N$ )

Output

Print N integers. The i-th number is the parent of vertex i. The parent of the root (vertex 1) must be printed as 0. The output must represent a valid rooted tree.

Only inputs where an answer exists are given.

Examples1

Example 1
Input
```
4 3
1 2 1
2 3 2
3 4 3
```
Expected output
```
0 1 2 3
```