Exploration Records

There is a tree with $N$ vertices numbered $1,2,\cdots,N$. The tree is rooted at vertex $1$.

There is a building of height $H_i$ at vertex $i$. Every height is a nonnegative integer and satisfies the following conditions.

• $H_1=0$.
• The heights of the buildings at the endpoints of every edge differ by exactly $1$.

An exploration robot moves from vertex $u$ to vertex $v$ along the simple path between them. When it traverses an edge and the height increases by $1$, it consumes $1$ unit of battery. When the height decreases by $1$, it gains $1$ unit of battery. The battery level must never become negative during the movement.

Define $A(u,v)$ as the minimum initial battery level that allows the robot to move from $u$ to $v$. If the robot starts with exactly $A(u,v)$ units of battery, let $Z(u$ be the first vertex at which its battery level is . The starting vertex is included when determining this first vertex. Let be the remaining battery level when the robot reaches during the same movement.

There are $M$ records of past explorations. Each record gives the values of $A(u,v)$, $B(u,v)$, and $Z(u,v)$ for a pair of vertices .

Find one assignment of heights $H_1,H_2,\cdots,H_N$ that is consistent with every record. If no such assignment exists, determine that it is impossible.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, print one line.

If a valid height assignment exists, print $N$ integers in the following format:

$H_1\ H_2\ \cdots\ H_N$

• $1 \le T \le 500$.
• $1 \le N \le 8\,000$.
• $0 \le M \le 8\,000$.