Республиканская олимпиада по информатике 2018 года за 9 класс | Казахстанские олимпиады

Задача A. Темные комнаты

У вас есть $n$ комнат, которые соединены $n$-$1$ коридорами. Известно, что с любой комнаты можно дойти до любой другой. В каждой комнате есть ровно одна лампочка. Есть $m$ кнопок пронумерованных от $1$ до $m$, кнопка с номером $i$ включает или выключает лампочки во всех комнатах на пути с комнаты $v_i$ до комнаты $u_i$. Состояние комнаты задается одним числом $0$ или $1$, где $0$ означает лампочка выключена, а $1$ означает, что она включена.

Алан пришел в гости к вам. Вы узнали, что Алан будет чуствовать себя как дома, если состояния комнат будут $a_1$, $a_2$, ..., $a_n$ для комнат от $1$ до $n$. Вы должны найти какие кнопки и в каком порядке нажимать, чтобы Алан чуствовал себя как дома. Так как вы не хотите заставлять ждать гостя, в последовательности не может быть больше чем $10^5$ кнопок. Если невозможно найти такую последовательность, вы должны вывести -$1$. Изначально все лампочки во всех комнатах выключены.

Формат входного файла

В первой строке входных данных задается одно целое число $n$ ($1 \le n \le 10^4$) — количество комнат. Во второй строке задаются $n$ чисел: $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i \le 1$) желаемое состояния комнат. Каждая из следующих $n$-$1$ строк описывает один коридор двумя целыми числами $v$ и $u$ ($1 \le u, v \le n$), что означает есть корридор между комнатами $v$ и $u$.

В следующей строке задается одно целое число $m$ ($1 \le m \le 10^4$) — количество кнопок. В каждой из следующих $m$ строк задается описание кнопок: в $i$-й строке описание $i$-й кнопки три целых числа $u_i$, $v_i$ и $t_i$, где $u_i$ и $v_i$ ($1 \le u_i, v_i \le n$) комнаты которые описывают путь, $t_i$ равно $0$, если кнопка выключает лампочки или $1$, если она включает лампочки.

Формат выходного файла

Выведите `-$1$'(без кавычек), если невозможно найти нужную последовательность. Иначе, выведите $l$ количество кнопок в последовательности и в следущей строке выведите $l$ чисел — номера кнопок в порядке из нажатия.

Примеры

Вход

6
1 1 0 0 1 1
1 2
1 3
3 4
3 5
4 6
4
1 2 1
2 5 1
3 4 0
1 6 1

Выход

3
4 2 3

Вход

3
0 0 1
1 3
1 2
1
1 3 1

Выход

-1