CF1904F.Beautiful Tree

Lunchbox has a tree of size $n$ rooted at node $1$ . Each node is then assigned a value. Lunchbox considers the tree to be beautiful if each value is distinct and ranges from $1$ to $n$ . In addition, a beautiful tree must also satisfy $m$ requirements of $2$ types:

• "1 a b c" — The node with the smallest value on the path between nodes $a$ and $b$ must be located at $c$ .
• "2 a b c" — The node with the largest value on the path between nodes $a$ and $b$ must be located at $c$ .

Now, you must assign values to each node such that the resulting tree is beautiful. If it is impossible to do so, output $-1$ .

The first line contains two integers $n$ and $m$ ( $2 \le n, m \le 2 \cdot 10^5$ ).

The next $n - 1$ lines contain two integers $u$ and $v$ ( $1 \le u, v \le n, u \ne v$ ) — denoting an edge between nodes $u$ and $v$ . It is guaranteed that the given edges form a tree.

The next $m$ lines each contain four integers $t$ , $a$ , $b$ , and $c$ ( $t \in \{1,2\}$ , $1 \le a, b, c \le n$ ). It is guaranteed that node $c$ is on the path between nodes $a$ and $b$ .

If it is impossible to assign values such that the tree is beautiful, output $-1$ . Otherwise, output $n$ integers, the $i$ -th of which denotes the value of node $i$ .