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$.

Lunchbox 有一棵大小为 $n$ 的树，根节点为节点 $1$。每个节点被赋予一个值。Lunchbox 认为这棵树是“优美的”，当且仅当所有节点的值互不相同，且取值范围恰好为 $1$ 到 $n$。此外，一棵优美的树还必须满足 $m$ 个约束条件，分为两类：

• “1 a b c” —— 节点 $a$ 与节点 $b$ 之间路径上值最小的节点必须是节点 $c$；
• “2 a b c” —— 节点 $a$ 与节点 $b$ 之间路径上值最大的节点必须是节点 $c$。

现在，请你为每个节点赋值，使得最终得到的树是优美的。若无法做到，请输出 $-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$.

第一行包含两个整数 $n$ 和 $m$（$2 \le n, m \le 2 \cdot 10^5$）。

接下来的 $n - 1$ 行每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n,\ u \ne v$），表示节点 $u$ 与节点 $v$ 之间存在一条边。保证所给的边构成一棵树。

接下来的 $m$ 行每行包含四个整数 $t$、$a$、$b$ 和 $c$（其中 $t \in \{1,2\}$，$1 \le a, b, c \le n$）。保证节点 $c$ 位于节点 $a$ 与节点 $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$.

如果无法为节点赋值使得树是优美的，则输出 $-1$。否则，输出 $n$ 个整数，其中第 $i$ 个整数表示节点 $i$ 的值。