408322: GYM103092 H Hard Life

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

Вот и настал тот самый день когда Абу впервые переступил порог Самого Дружного Университета (СДУ) распахнув перед собой двери к бесценным знаниям. С первых же дней в стенах нового для себя заведения он начал всех удивлять своими знаниями и навыками в программировании. Все сокурсники завидовали ему, а учителя гордились что к ним в универ поступил такой сильный студент и видели в нём нового Илона Маска.

А тем временем Абу, вместо того чтобы учиться ещё усерднее пошел по пути лентяя. Пока он разгуливал уроки лучик его звезды тихо угасал, и не прошло и семестра как все уже догнали его по учёбе. Вдобавок ко всему этому, во время сессии он сильно затруднялся и с первого же раза схватил ретейк и свалился со стипендии. Теперь перед ним стоит непростая задача — найти выход и оплатить за ретейк самому, потому что он не хотел разглашать свой триумфальный провал своим родителям.

Абу, идя домой, весь опустошённый, по дороге увидел группу людей, собравшихся в большую кучу. А посередине увидел стоявшего в классическом костюме человека похожего на профессора.

- Слушайте, студенты! Того, кто решит мою задачу первым, я возьму к себе в ассистенты и буду выплачивать ему большую сумму! – громко огласил профессор. Абу, с загоревшимися глазами, умчался в эту толпу, чтобы попытать своё счастье. В оригинальной формулировке задача звучала так:

У вас есть перестановка $$$p$$$ целых чисел от $$$1$$$ до $$$n$$$. А также у вас есть $$$m$$$ пар целых чисел $$$(a_i, b_i)$$$. За одну операцию вам разрешено выбрать произвольное целое число $$$i$$$ ($$$1 \le i \le m$$$) и сделать операцию swap(p[a[i]], p[b[i]]). Другими словами, вы меняете местами значения на позициях $$$a_i$$$ и $$$b_i$$$.

Есть одно важное ограничение — четность суммарного количества использований $$$i$$$-й пары во всех ваших операциях должна быть в точности равна $$$c_i$$$.

Вам нужно сделать $$$p$$$ лексикографически минимальным за не более $$$600000$$$ операций, при этом соблюдая все ограничения. Абу надеется на вашу помощь. На кону стоит его ретейк!

Входные данные

В первой строке входного файла даны два целых числа $$$n$$$ и $$$m$$$ — размер перестановки и кол-во пар ($$$2 \le n \le 1000$$$, $$$1 \le m \le 10000$$$).

Во второй строке входного файла даны $$$n$$$ целых чисел $$$p_1$$$, ..., $$$p_n$$$ разделенные пробелами ($$$1 \le p_i \le n$$$, $$$p_i \neq p_j$$$ если $$$i \neq j$$$).

В следующих $$$m$$$ строках даны тройки целых чисел $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ — пара и требуемая четность количества её использований ($$$1 \le a_i, b_i \le n$$$, $$$a_i \neq b_i$$$, $$$0 \le c_i \le 1$$$).

Выходные данные

В первой строке выведите $$$p_1$$$, ..., $$$p_n$$$ после всех ваших изменений. Она должна быть лексикографически минимальной.

Во второй строке выведите $$$k$$$ — кол-во использованных вами операций ($$$0 \le k \le 600000$$$).

В следующей строке выведите ровно $$$k$$$ целых чисел $$$q_1$$$, ..., $$$q_k$$$ ($$$1 \le q_i \le m$$$). $$$q_i$$$ должно обозначать номер пары, которую вы использовали для $$$i$$$-й операции. Если $$$k = 0$$$, ничего выводить не надо.

ПримерыВходные данные

4 6
4 2 3 1
1 2 1
2 4 1
3 4 1
2 3 1
1 4 1
1 3 1

Выходные данные

1 2 4 3
6
4 5 6 3 2 1

Входные данные

4 10
4 2 1 3
2 4 1
1 3 0
4 1 0
3 4 1
2 1 0
3 4 0
1 2 1
1 3 1
2 4 1
1 3 1

Выходные данные

1 2 3 4
6
1 8 7 9 4 10