310885: CF1904F. Beautiful Tree

Memory Limit:512 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Beautiful Treetime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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

Input

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

Output

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

ExamplesInput
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
Output
1 6 7 5 3 4 2 
Input
2 2
1 2
1 1 2 1
1 1 2 2
Output
-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的值。

加入题单

上一题 下一题 算法标签: