28349번 - 쿼리와 트리 1 스페셜 저지

문제

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

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

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

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

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 이후 다음과 같은 형태의 입력이 T개 주어진다.

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

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

한 입력에서 N의 합은 16276 이하이다.

한 입력에서 M의 합은 33043 이하이다.

출력

T개의 줄에 걸쳐 각 테스트 케이스의 정답을 출력하라. 각 테스트 케이스에 대해:

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

제한

힌트