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

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

Ограничение по времени Ограничение по памяти
2 секунды 256 мегабайт

У вас есть nn комнат, которые соединены nn-11 коридорами. Известно, что с любой комнаты можно дойти до любой другой. В каждой комнате есть ровно одна лампочка. Есть mm кнопок пронумерованных от 11 до mm, кнопка с номером ii включает или выключает лампочки во всех комнатах на пути с комнаты viv_i до комнаты uiu_i. Состояние комнаты задается одним числом 00 или 11, где 00 означает лампочка выключена, а 11 означает, что она включена.

Алан пришел в гости к вам. Вы узнали, что Алан будет чуствовать себя как дома, если состояния комнат будут a1a_1, a2a_2, ..., ana_n для комнат от 11 до nn. Вы должны найти какие кнопки и в каком порядке нажимать, чтобы Алан чуствовал себя как дома. Так как вы не хотите заставлять ждать гостя, в последовательности не может быть больше чем 10510^5 кнопок. Если невозможно найти такую последовательность, вы должны вывести -11. Изначально все лампочки во всех комнатах выключены.

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

В первой строке входных данных задается одно целое число nn (1n1041 \le n \le 10^4) — количество комнат. Во второй строке задаются nn чисел: a1a_1, a2a_2, ..., ana_n (0ai10 \le a_i \le 1) желаемое состояния комнат. Каждая из следующих nn-11 строк описывает один коридор двумя целыми числами vv и uu (1u,vn1 \le u, v \le n), что означает есть корридор между комнатами vv и uu.

В следующей строке задается одно целое число mm (1m1041 \le m \le 10^4) — количество кнопок. В каждой из следующих mm строк задается описание кнопок: в ii-й строке описание ii-й кнопки три целых числа uiu_i, viv_i и tit_i, где uiu_i и viv_i (1ui,vin1 \le u_i, v_i \le n) комнаты которые описывают путь, tit_i равно 00, если кнопка выключает лампочки или 11, если она включает лампочки.

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

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

Примеры

Вход

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