| Codeforces Round 259 (Div. 1) |
|---|
| Закончено |
Twilight Sparkle узнала, что злая Nightmare Moon вернется во время предстоящего торжества летнего солнца после тысячелетнего заточения на луне. Она попыталась предупредить свою наставницу, принцессу Celestia, но принцесса проигнорировала ее и отправила в Ponyville, проверить как идет подготовка к торжеству.
Twilight Sparkle хочет выследить Nightmare Moon. К сожалению, она не знает, каким именно путем пойдет Nightmare Moon. К счастью, для каждого места в Ponyville Twilight Sparkle знает: четное или нечетное количество раз посетит его Nightmare Moon. Можете ли вы помочь Twilight Sparkle найти любой путь, который будет удовлетворять этим данным?
Ponyville может быть представлен как неориентированный граф без петлей и мульти-ребер (вершины — это места в Ponyville, ребра — это дороги, соединяющие места). Разрешается начать и закончить путь в любых местах (также, возможно, путь будет пустой). Одно место можно посетить несколько раз. Путь не должен посетить больше, чем 4n мест Ponyville.
Первая строка содержит два целых числа, n и m (2 ≤ n ≤ 105; 0 ≤ m ≤ 105) — количество мест и дорог в Ponyville. Каждая из следующих m строк содержит два целых числа: ui, vi (1 ≤ ui, vi ≤ n; ui ≠ vi), эти числа обозначают дорогу между местами ui и vi.
Следующая строка содержит n целых чисел: x1, x2, ..., xn (0 ≤ xi ≤ 1) — четность количества посещений для каждого места. Если xi = 0, то i-е место нужно посетить четное число раз, иначе — нечетное число раз.
Выведите число посещенных мест k в первой строке (0 ≤ k ≤ 4n). Затем выведите k целых чисел — номера мест в порядке посещения их путем. Если xi = 0, то в данном пути место i должно встретиться четное число раз, иначе i-е место должно встретиться в нем нечетное число раз. Обратите внимание, что система дорог Ponyville не содержит петель, поэтому в выведенном пути любые два соседних места должны быть различны.
Если требуемого пути не существует, выведите -1. Если существует несколько правильных путей, можете вывести любой из них.
3 2
1 2
2 3
1 1 1
3
1 2 3
5 7
1 2
1 3
1 4
1 5
3 4
3 5
4 5
0 1 0 1 0
10
2 1 3 4 5 4 5 4 3 1
2 0
0 0
0
