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