F. Прекрасное дерево
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Ланчбокса есть дерево размера $$$n$$$ с корнем в вершине $$$1$$$. Каждой вершине присваивается значение. Ланчбокс считает дерево прекрасным, если каждое значение является уникальным и находится в диапазоне от $$$1$$$ до $$$n$$$. Кроме того, прекрасное дерево должно удовлетворять $$$m$$$ требованиям $$$2$$$ типов:

  • «1 a b c» — Вершина с наименьшим значением на пути между вершинами $$$a$$$ и $$$b$$$ должна быть $$$c$$$.
  • «2 a b c» — Вершина с наибольшим значением на пути между вершинами $$$a$$$ и $$$b$$$ должна быть $$$c$$$.

Теперь вы должны присвоить значения каждой вершине так, чтобы получившееся дерево было прекрасным. Если это невозможно, выведите $$$-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