Under construction

Still being built. Things may change

Queries and Trees 1

Time limit1sMemory limit1024 MB

Summary
Given M vertex pairs and their lowest common ancestors in an unknown rooted tree of N vertices, print any tree that matches all pairs, or NIE if none exists.
Level

Medium7 of 10

Topics
Tree, Backtracking, Brute force
Solved
No attempts yet

문제

A tree with N vertices (2 ≤ N ≤ 60) is given. Each vertex is numbered from 1 to N, and one of the vertices is the root.

You, who like trees and queries, chose M pairs of nodes (1 ≤ M ≤ 120) and computed the lowest common ancestor of each pair.

However, you do not actually know what the tree looks like.

Given the M pairs and their lowest common ancestors, print any tree that satisfies all of this information. If no such tree exists, print NIE.

입력

The first line contains the number of test cases T. Then T test cases follow, each in the format below.

The first line of a test case contains two integers N and M.

Each of the next M lines contains u, v, w, meaning the lowest common ancestor of vertices u and v is vertex w. (1 ≤ u, v, w ≤ N, u ≠ v)

In one input, the sum of N is at most 16276.

In one input, the sum of M is at most 33043.

출력

For each test case, print one line. If no such tree exists, print NIE. Otherwise, print N integers. The i-th integer is the parent of vertex i. The root must print 0. The output must describe a valid rooted tree.

Examples1

  1. Example 1

    Input
    7
3 1
1 2 3
3 3
1 2 2
2 3 3
3 1 1
4 2
2 1 2
1 4 3
4 3
1 2 1
2 3 2
3 4 3
6 3
2 4 3
6 5 4
1 2 6
7 4
7 3 5
4 1 2
6 3 6
6 4 5
12 9
1 5 7
11 2 6
9 4 12
8 12 6
10 1 7
4 3 12
3 10 6
8 11 8
2 5 10
    Expected output
    3 3 0
NIE
3 0 2 3
0 1 2 3
NIE
2 0 6 5 2 5 5
7 10 12 12 10 0 6 6 12 7 8 6