Codeforces Round 149 (Div. 2) |
---|
Закончено |
У Валеры имеется n счетчиков, пронумерованных от 1 до n. Некоторые из них соединены проводами, также на каждом из счетчиков имеется специальная кнопка.
Изначально, во всех счетчиках записано число 0. При нажатии кнопки, расположенной на некотором счетчике, записанное в нем значение увеличивается на единицу. Также значения, записанные во всех счетчиках, непосредственно соединенных с ним проводом, увеличиваются на единицу.
Валера и Игнат затеяли небольшой спор, заключающийся в следующем. Игнат загадал последовательность из n целых чисел a1, a2, ..., an. Валере нужно выбрать некоторый набор различных счетчиков и нажать кнопки на каждом из них ровно по одному разу (на остальных счетчиках кнопки останутся не нажатыми). Если после этого найдется счетчик с номером i, в котором записано значение равное ai, то Валера проигрывает спор, иначе он побеждает в споре.
Помогите Валере определить, на каких счетчиках нужно нажать кнопки, чтобы выиграть спор.
В первой строке через пробел записаны два целых числа n и m (1 ≤ n, m ≤ 105), обозначающие количество счетчиков у Валеры и количество пар счетчиков, соединенных проводами, соответственно.
В каждой из следующих m строк через пробел записаны два целых числа ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi), которые обозначают, что счетчики с номерами ui и vi соединены проводом. Гарантируется, что каждая пара соединенных счетчиков встречается во входных данных ровно один раз.
В последней строке через пробел записаны n целых чисел a1, a2, ..., an (0 ≤ ai ≤ 105), где ai — значение, которое загадал Игнат для i-го счетчика.
Если Валера не сможет победить в споре, выведите в первой строке -1.
В противном случае в первой строке выведите целое число k (0 ≤ k ≤ n). Во второй строке выведите через пробел k различных целых чисел — номера счетчиков, на которых Валере нужно нажать кнопки, чтобы выиграть спор, в любом порядке.
Если существует несколько ответов, выведите любой.
5 5
2 3
4 1
1 5
5 3
2 1
1 1 2 0 2
2
1 2
4 2
1 2
3 4
0 0 0 0
3
1 3 4
Название |
---|