У Ланчбокса есть дерево размера \(n\) с корнем в вершине \(1\). Каждой вершине присваивается значение. Ланчбокс считает дерево прекрасным, если каждое значение является уникальным и находится в диапазоне от \(1\) до \(n\). Кроме того, прекрасное дерево должно удовлетворять \(m\) требованиям \(2\) типов:
- «1 a b c» — Вершина с наименьшим значением на пути между вершинами \(a\) и \(b\) должна быть \(c\).
- «2 a b c» — Вершина с наибольшим значением на пути между вершинами \(a\) и \(b\) должна быть \(c\).
Теперь вы должны присвоить значения каждой вершине так, чтобы получившееся дерево было прекрасным. Если это невозможно, выведите \(-1\).
Выходные данные
Если невозможно присвоить значения так, чтобы дерево было прекрасным, выведите \(-1\). В противном случае выведите \(n\) целых чисел, \(i\)-е из которых обозначает значение вершины \(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 6 7 5 3 4 2
|
|
2
|
2 2
1 2
1 1 2 1
1 1 2 2
|
-1
|