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

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

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