CF1904F.Beautiful Tree
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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≤n,m≤2⋅105 ).
The next n−1 lines contain two integers u and v ( 1≤u,v≤n,u=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∈{1,2} , 1≤a,b,c≤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 .
输入输出样例
输入#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