0411. Гирлянда

Имя входного файла:	bulbs.in
Имя выходного файла:	bulbs.out
Ограничение по времени:	1 s
Ограничение по памяти:	256 megabytes

Ярополк подарил Святославу на прошедший Новый Год чудесную гирлянду. Гирлянда представляет из себя ориентированный ациклический граф из N вершин и M ребер, в каждой вершине которого есть лампочка, которая может быть включена или выключена, и переключатель. При нажатии на переключатель состояние лампочки в этой вершине и во всех из неё достижимых меняется на противоположное (лампочка включается, если была выключена и выключается, если была включена). Когда Святослав достал гирлянду из коробки, некоторые лампочки уже были включены. Теперь Святославу интересно какое наибольшее число лампочек на его гирлянде может гореть одновременно, какое минимальное количество нажатий на выключатели требуется для этого сделать и последовательность нажатий, которая приведет к желаемому результату. Ваша задача - помочь ему с этим.

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

В первой строке входного файла два числа N и M - количество вершин и ребер соответственно, 1 ≤ N, M ≤ 20000. Далее следует M строк, в каждой из которых два числа u и v, обозначающие соответствующее ребро. Далее следует строка, содержащая N чисел a_i, a_i = 0, если i-я лампочка изначально выключена, a_i = 1, если включена.

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

В первой строке выведите 2 числа N₁ - максимальное количество лампочек, которое может загореться, K - соответствующее минимальное требуемое количество нажатий на выключатели. Во второй строке выведите K чисел - последовательность нажатий.

Пример:

bulbs.in	bulbs.out
3 2 1 2 1 3 0 0 0	3 1 1
3 2 1 2 1 3 1 0 0	3 2 2 3

Источник: Чемпионат ПетрГУ по программированию. 1 марта 2015 года

Обсудить       Отправить решение



Версия для печати