Решения: Республиканская олимпиада, Заключительный этап

2018 учебный год

(Қараңғы бөлмелер)

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

2 seconds

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

256 megabytes

Сізде

$n$ -

$1$ дәліз арқылы қосылған

$n$ бөлме бар. Әр бөлмеден, әр бөлмеге жетуге болатыны белгілі. Әр бөлмеде бір шам бар.

$1$ -ден

$m$ -ға дейін нөмірленген

$m$ батырма бар.

$i$ -ші батырма

$v_i$ бөлмесінен

$u_i$ бөлмесіне дейінгі жолында шамдарды өшіреді немесе қосады. Әр бөлменің күйі бір санмен көрсетіледі:

$0$ немесе

$1$ , осында

$0$ шамның өшірілгенін, ал

$1$ шамның қосылып тұрғанын көрсетеді. Сіздің үйіңізге Алан қонаққа келді. Нөмірлері

$1$ -ден

$n$ -ға дейінгі бөлмелердің күйлері

$a_1$ ,

$a_2$ , ...,

$a_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 \le n \le 100, 1 \le m \le 8$ . Бөлім $11$ ұпайға бағаланады.
$1 \le n,m \le 2000$ және барлық батырма үшін $t_i = 1$ . Бөлім $15$ ұпайға бағаланады.
$1 \le n,m \le 500$ . Бөлім $19$ ұпайға бағаланады.
$1 \le n,m \le 10^4$ және $i$ -ші дәліз $i$ және $i + 1$ бөлмелерді қосады. Бөлім $25$ ұпайға бағаланады.
$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

Вход

Ответ

-1

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

посмотреть в олимпиаде

Комментарий/решение: