| VK Cup 2012 Раунд 3 |
|---|
| Закончено |
Непроста жизнь самой обычной переменной по имени Вася. Куда бы она ни отправилась, ей то присваивают значение, то просто игнорируют, то вообще используют!
Жизнь Васи проходит в состояниях программы, в которой ей случилось быть объявленной. В каждом состоянии Васю могут либо использовать (например, для вычисления значения другой переменной), либо присваивать ей значение, либо игнорировать. Между некоторыми состояниями есть ориентированные переходы.
Путь — это последовательность состояний v1, v2, ..., vx, где для каждого 1 ≤ i < x существует переход из vi в vi + 1.
Значение Васи в состоянии v интересует окружающий мир, если существует путь p1, p2, ..., pk такой, что pi = v для некоторого i (1 ≤ i ≤ k), в состоянии p1 Васе присваивают значение, в состоянии pk Васю используют и ни в каких состояниях pi, кроме p1, Васе не присваивают значение.
Помогите Васе: найдите состояния, в которых значение Васи интересует окружающий мир.
В первой строке через пробел записаны два целых числа n и m (1 ≤ n, m ≤ 105) — количества состояний и переходов, соответственно.
Во второй строке через пробел записаны n целых чисел f1, f2, ..., fn (0 ≤ fi ≤ 2), fi описывает действия над Васей в состоянии номер i: 0 соответствует игнорированию, 1 — присваиванию значения, 2 — использованию.
В следующих m строках через пробел записаны пары целых чисел ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), каждая пара задает переход из состояния с номером ai в состояние с номером bi. Между двумя состояниями может быть любое количество переходов.
Выведите n целых чисел r1, r2, ..., rn, разделенных пробелами или переводами строк. Число ri должно быть равно 1, если значение Васи в состоянии номер i интересует окружающий мир, и равно 0 в противном случае. Состояния нумеруются от 1 до n в том же порядке, в котором заданы их описания во входных данных.
4 3
1 0 0 2
1 2
2 3
3 4
1
1
1
1
3 1
1 0 2
1 3
1
0
1
3 1
2 0 1
1 3
0
0
0
В первом примере из состояний программы можно составить единственный путь, в котором значение Васи интересует окружающий мир, 1 
2 3 4; в него входят все состояния, поэтому во всех них значение Васи интересует окружающий мир.
Во втором примере единственный путь, в котором значение Васи интересует окружающий мир, — 1 3; состояние 2 в него не входит.
В третьем примере из состояний нельзя составить ни одного пути, в котором значение Васи интересует окружающий мир, поэтому значение Васи никогда не интересует окружающий мир.
