310885: CF1904F. Beautiful Tree
Description
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$.
InputThe 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$.
OutputIf 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$.
ExamplesInput7 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 2Output
1 6 7 5 3 4 2Input
2 2 1 2 1 1 2 1 1 1 2 2Output
-1
Output
Lunchbox有一棵大小为n的树,以节点1为根。每个节点都会被分配一个值。Lunchbox认为如果每个值都是独一无二的,并且范围从1到n,那么这棵树就是美丽的。此外,一棵美丽的树还必须满足m个要求,这些要求分为2种类型:
1. "1 a b c" —— 节点a和节点b之间的路径上值最小的节点必须位于c。
2. "2 a b c" —— 节点a和节点b之间的路径上值最大的节点必须位于c。
现在,您必须给每个节点赋值,使得结果树是美丽的。如果不可能做到这一点,请输出-1。
输入数据格式:
第一行包含两个整数n和m(2 ≤ n, m ≤ 2 * 10^5)。
接下来的n-1行,每行包含两个整数u和v(1 ≤ u, v ≤ n,u ≠ v),表示节点u和节点v之间的边。保证给定的边构成一棵树。
接下来的m行,每行包含四个整数t、a、b和c(t ∈ {1,2},1 ≤ a, b, c ≤ n)。保证节点c位于节点a和节点b之间的路径上。
输出数据格式:
如果无法赋值使得树是美丽的,输出-1。否则,输出n个整数,第i个数表示节点i的值。题目大意: Lunchbox有一棵大小为n的树,以节点1为根。每个节点都会被分配一个值。Lunchbox认为如果每个值都是独一无二的,并且范围从1到n,那么这棵树就是美丽的。此外,一棵美丽的树还必须满足m个要求,这些要求分为2种类型: 1. "1 a b c" —— 节点a和节点b之间的路径上值最小的节点必须位于c。 2. "2 a b c" —— 节点a和节点b之间的路径上值最大的节点必须位于c。 现在,您必须给每个节点赋值,使得结果树是美丽的。如果不可能做到这一点,请输出-1。 输入数据格式: 第一行包含两个整数n和m(2 ≤ n, m ≤ 2 * 10^5)。 接下来的n-1行,每行包含两个整数u和v(1 ≤ u, v ≤ n,u ≠ v),表示节点u和节点v之间的边。保证给定的边构成一棵树。 接下来的m行,每行包含四个整数t、a、b和c(t ∈ {1,2},1 ≤ a, b, c ≤ n)。保证节点c位于节点a和节点b之间的路径上。 输出数据格式: 如果无法赋值使得树是美丽的,输出-1。否则,输出n个整数,第i个数表示节点i的值。