쿼리와 트리 2

시간 제한3초메모리 제한1024 MB

요약

루트가 1번인 트리의 구조를 모른 채 정점 쌍 M개와 각 쌍의 최소 공통 조상이 주어집니다. 각 정점의 부모를 출력합니다.

문제

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

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

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

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

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

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

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