Link Cut Tree

View as PDF

Submit solution

Points: 50
Time limit: 4.0s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Larry was playing with a link cut tree last night. He has made Q LCA queries to his link cut tree. Each time, the link cut tree responded with the integer representing the lowest common ancestor. He cut one too many edges and now he can't restore his tree. However, he will be satisfied with any tree that will give him the same results when asked the LCA queries again. Your task is to help him restore his tree. You will be given the Q queries, and the result of those queries.

Input Specification

On the first line, two integers, N and Q (1 \le N, Q \le 10^5) where N is the number of nodes.

On the next Q lines, three integers u_i v_i and w_i, which indicates that the LCA of u_i and v_i is w_i. (1 \le u_i, v_i, w_i \le N).

Output Specification

N integers, indicating that the parent of i is p_i. (e.g. if the first integer is 2, then the parent of 1 is 2, if the second integer is 5, then the parent of 2 is 5). Node 1 is always the root, and has special value 0 as the parent. In other words, p_1 = 0.

Sample Input

4 3
1 2 1
2 3 2
3 4 3

Sample Output

0 1 2 3


There are no comments at the moment.