Codeforces Round 914 (Div. 2) |
---|
Закончено |
У Ланчбокса есть дерево размера $$$n$$$ с корнем в вершине $$$1$$$. Каждой вершине присваивается значение. Ланчбокс считает дерево прекрасным, если каждое значение является уникальным и находится в диапазоне от $$$1$$$ до $$$n$$$. Кроме того, прекрасное дерево должно удовлетворять $$$m$$$ требованиям $$$2$$$ типов:
Теперь вы должны присвоить значения каждой вершине так, чтобы получившееся дерево было прекрасным. Если это невозможно, выведите $$$-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$$$.
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 6 7 5 3 4 2
2 2 1 2 1 1 2 1 1 1 2 2
-1
Название |
---|