Lunchbox 有一个大小为 $$$n$$$ 的树,根节点为 $$$1$$$。然后为每个节点分配一个值。如果每个值都不同并且范围从 $$$1$$$ 到 $$$n$$$,那么 Lunchbox 认为这棵树很漂亮。此外,一棵美丽的树还必须满足$$$2$$$类型的$$$m$$$要求:
- "1 a b c" — 节点 $$$a$$$ 和 $$$b$$$ 之间的路径上具有最小值的节点必须位于 $$$c$$$。
- "2 a b c" — 节点 $$$a$$$ 和 $$$b$$$ 之间的路径上具有最大值的节点必须位于 $$$c$$$。
现在,您必须为每个节点分配值,以便生成的树很漂亮。如果不可能,则输出$$$-1$$$。
输入
第一行包含两个整数 $$$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$$$ 之间的路径上。
输出
如果无法分配使树漂亮的值,则输出 $$$-1$$$。否则,输出 $$$n$$$ 个整数,其中第 $$$i$$$ 表示节点 $$$i$$$ 的值。
示例
输入 #1
7 5 1 2 1 3 1 4 3 5 4 6 3 7 1 6 5 1 2 6 7 3 1 2 7 1 1 7 5 7 2 4 2 2
输出 #1
1 6 7 5 3 4 2
输入 #2
2 2 1 2 1 1 2 1 1 1 2 2
输出 #2
-1