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. $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

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