問題文

フェースィッターというアプリは、画像を投稿するアプリです。

誰かが画像を投稿すると、画像を投稿した人と、その人と友達関係にある人はその画像を見ることが出来ます。

また、誰かの投稿した画像を見た人はリスィットをすることができます。

画像をリスィットすると、画像を投稿した人の友達関係にある人だけでなく、リスィットした人と友達関係にある人もその画像を見ることが出来ます。

このフェースィッターに新たに \(N\) 人が登録しました。それぞれの人にはユーザー名が \(1\) から \(N\)まで設定されています。

ユーザーには「自分が初めて見た画像は必ずリスィットする人」と「絶対にリスィットしない人」の2パターンがあります。

フェースィッターを運営するスランナはフェースィッターの円滑さを知りたいので、ユーザー \(i\) が画像を投稿した時に何人が見れるかを \(1\) 以上 \(N\) 以下の全ての \(i\) について知りたいです。

しかし、彼女が一人ひとりそれを調べていると時間がかかってしまいます。

そこで、彼女は友人であるあなたにプログラムの作成をお願いしてきました。あなたは彼女のためにプログラムを書いてあげましょう。

入力

1行目には \(N\) と \(M\) が空白区切りで与えられます。

2行目には長さ \(N\) の文字列が与えられます。左から \(i\) 文字目の文字が1の場合はユーザー \(i\)　は「自分が初めて見た画像は必ずリスィットする人」、0の場合はユーザー \(i\) は「絶対にリスィットしない人」です。

3行目以降の \(M\) 行にはフェースィッター使用者の友達関係が入力されます。

　\(i+2\) 行目 \((1≦i≦M)\) には \(i\) 番目の友達関係が入力され、ユーザー \(a_i\) とユーザー \(b_i\) が友達関係であることを表します。

出力

\(N\) 行出力して下さい。

\(i\) 行目には、ユーザー \(i\) が画像を投稿した時にその画像を見ることが出来る人数を出力して下さい。

制約

• \(1≦N≦100,000\)


• \(1≦M≦200,000\)


• \(1≦a_i, b_i≦N\)


• \(a_i≠b_i\)


• \(i≠j\) なら \((a_i, b_i)≠(b_j, a_j)\) かつ \((a_i, b_i)≠(a_j, b_j)\)

小課題

小課題 Small

• \(1≦N≦200\)


• \(1≦M≦300\)

小課題 Large

• \(1≦N≦3,000\)


• \(1≦M≦5,000\)

小課題 Euglena

• 追加の制約はない。