쿼리와 트리 1
시간 제한1초메모리 제한1024 MB
정점 N개인 루트 트리에서 M개 쌍의 최소 공통 조상이 주어질 때, 모든 조건을 만족하는 트리의 부모 배열을 출력하고 그런 트리가 없으면 NIE를 출력합니다.
문제
정점 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 이하이다.
출력
각 테스트 케이스에 대해 한 줄을 출력하라. 그러한 트리가 없다면 NIE를 출력하라. 있다면 N개의 정수를 출력하라. i번째 정수는 i번 정점의 부모 정점이다. 루트에 대해서는 0을 출력해야 한다. 출력은 올바른 루트 있는 트리를 나타내야 한다.