Dobrodošli u Vatrograd, grad s najviše vatrogasnih postaja po broju stanovnika! Glavni vatrogasac vatrogasne postrojbe Vatrograda Vatroslav našao se u problemu te mu je potrebna vaša pomoć. Vatroslava zanima, za bilo koju kuću u Vatrogradu, koliko je od kuće udaljena najbliža vatrogasna postaja.

Vatrograd je reprezentiran neusmjerenim grafom sa \(n\) vrhova i \(m\) bridova, gdje svaki vrh predstavlja kuću (0) ili vatrogasnu postaju (1), a svaki brid predstavlja cestu koja ih povezuje. Udaljenost između susjednih vrhova povezanih bridom iznosi \(1\). Vaš zadatak je redom za svaku kuću (0) ispisati udaljenost do najbliže vatrogasne postaje. Garantirano je da će graf biti povezan te da će postojati barem jedna kuća i barem jedna vatrogasna postaja.

Ulazni podatci

U prvome retku nalaze se prirodni brojevi \(n\) (\(2 \leq n \leq 2 \cdot 10^5\)) i \(m\) (\(1 \leq m \leq 2 \cdot 10^5\)).

U drugome retku nalazi se binarni string duljine \(n\) koji označava vrstu i-tog vrha: kuća (0) ili vatrogasna postaja (1).

U sljedećih m redaka navedeni su bridovi grafa, određeni vrhovima \(u_i\) \(v_i\) (\(1 \leq u_i,v_i \leq 2 \cdot 10^5\)).

Izlazni podatci

Ispišite odgovore odvojene razmakom za svaki vrh koji je kuća (0) redoslijedom njihovih indeksa.

Podzadatci

Ulaz primjera 1

7 6
1000100
1 2
2 3
2 4
2 5
5 6
5 7

Izlaz primjera 1

1 2 2 1 1

Pojašnjenje primjera 1

Vrhovi \(1\) i \(5\) se ne ispisuju jer su vatrogasne postaje, udaljenst do najbliže vatrogasne postaje vrha \(2\) je \(1\), za vrhove \(3\), \(4\) udaljenost je \(2\) te je za vrhove \(6\), \(7\) udaljenost \(1\).

Ulaz primjera 2

5 8
00001
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 5

Izlaz primjera 2

1 1 1 2

Ulaz primjera 3

8 8
00100100
1 4
1 6
2 5
2 7
3 4
3 6
5 6
7 8

Izlaz primjera 3

1 2 1 1 3 4