У Ланчбокса есть дерево размера \(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
4000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач