28350번 - 쿼리와 트리 2 스페셜 저지

문제

N(1 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 1번 정점은 루트이다.

트리와 쿼리를 좋아하는 당신은 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개를 주고, 두 노드의 가장 가까운 공통 조상이 무엇인지 계산하였다.

하지만 사실 당신은 그 트리가 무엇인지 모른다.

두 노드의 쌍과, 가장 가까운 공통 조상 정보가 M개 주어질 때, 이 정보를 만족하는 트리를 아무거나 출력하여라.

입력

첫 번째 줄에 두 정수 N, M이 주어진다.

이후 M개의 줄에 정보 u, v, w가 주어진다. u번 정점과 v번 정점의 가장 가까운 공통 조상이 w번 정점이라는 정보이다. (1 ≤ u, v, w ≤ N)

출력

N개의 정수를 출력하라. 이 중 i번째 수는 i번 노드의 부모 노드를 뜻한다. 루트 노드 (1번 노드) 에 대해서는, 0을 출력해야 한다. 출력은 올바른 루트 있는 트리를 표현해야 한다.

답이 항상 존재하는 입력만이 주어진다.

제한

힌트