Республиканская олимпиада по информатике. 2018 год

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

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

У вас есть $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$ чисел — номера кнопок в порядке из нажатия.

Система оценки

Данная задача содержит пять подзадач:

1. $1 \le n \le 100, 1 \le m \le 8$. Оценивается в $11$ баллов.
2. $1 \le n,m \le 2000$ и $t_i = 1$ для всех кнопок. Оценивается в $15$ баллов.
3. $1 \le n,m \le 500$. Оценивается в $19$ баллов.
4. $1 \le n,m \le 10^4$ и $i$-й коридор соединяет комнаты $i$ и $i + 1$. Оценивается в $25$ баллов.
5. $1 \le n,m \le 10^4$. Оценивается в $30$ баллов.

Пример:

s Вход

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

Замечание

{ \center \includegraphics[width=1.0\textwidth]{sample.eps}
} ( Yerzhan Utkelbayev )