G - 1 Bird on Cherry Blossoms

2 secs 1024 MB
matcharate12's icon matcharate12

※この問題で Python 言語を用いる方は極力、提供されている Python 言語のコンパイル種類である pypy を選んで提出してください。CPython を選んで提出すると、実装方法によっては TLE になる可能性があります。

Story

🌸

RT Robot も満足気にキッチンに戻りました。かなり活発に仕事をしているようで、matcharate君たちは非常に助かっています。

今日も、この茶屋は閉店の時間がやってきました。お客さんたちは満足気に帰っていき、tearate君はなんだかホッとしたようです。
matcharate君は、茶屋沿いの広い通りに桜木がたくさん並べられているのを見ました。しかし、なんでしょう...?この桜にある花びら、種類がたくさんありますね...

あ、小鳥も桜を見に来たようです。でもなかなか可愛い小鳥の赤ちゃんなので、桜の木から他の木までは飛べないようです。

桜が舞う中、matcharate君とtearate君は小鳥を見ながら、広い通りを歩いて自分たちの家へ帰っていきました。

:

end.🐣

問題

NN 頂点 MM 辺の単純無向グラフが与えられます。
各頂点には 1,2,...,N1,2,...,N と番号づけられており、i (1iM)i\ (1\le i\le M) 本目の辺では頂点 Ai,BiA_i,B_i を相互に繋いでいます。
また各頂点には整数が 11 つずつ置かれており、頂点 j (1jN)j\ (1\le j\le N) には整数 WjW_j が置かれています。ここで与えられるグラフが必ずしも連結であるとは限りません。

小鳥は以下の行動を順に行います。

  • 11 以上 NN 以下の整数 aa を選び、頂点 aa に舞い降りる。その頂点に置かれている整数を集める。
  • その後、以下の行動を 00 回以上好きなだけ繰り返す
    • 今いる頂点に隣接している辺をランダムに 11 つ選ぶ。選んだ辺の上を渡ってその辺に隣接する別の頂点に移動し、移動先の頂点に置かれている整数を集める。

以下の質問において、k=0,1,2,...,Nk=0,1,2,...,N に対する答えを求めてください。

  • 小鳥がちょうど kk 種類の素数を集めることができるような行動の仕方は存在しますか?

入力

入力は以下の形式で与えられる。

NNMM
W1W_1W2W_2\dotsWNW_N
A1A_1B1B_1
A2A_2B2B_2
\vdots
AMA_MBMB_M

制約

  • 2N10002\le N\le 1000
  • 0Mmin(1000,N(N1)2)0\le M\le \min (1000,\frac{N(N-1)}{2})
  • 1Wj1091\le W_j\le 10^9WjW_j はすべて異なる
  • 1AiBiN1\le A_i\neq B_i\le Nmnm\neq n ならば (Am,Bm)(An,Bn)(A_m,B_m)\neq (A_n,B_n)
  • 入力はすべて整数
  • 与えられるグラフは単純である、すなわち二重辺、自己ループを含まないグラフである

出力

N+1N+1 行出力せよ。i (1iN+1)i\ (1\le i\le N+1) 行目には上の質問において k=i1k=i-1 のときの質問の答えに対し、
条件を満たす行動の方法が存在するなら Yes 、存在しないなら No を出力せよ。

入出力例

入力例1
6 5
1 2 3 4 5 6
1 2
2 3 
2 4
4 5
5 6
出力例1
Yes
Yes
Yes
Yes
No
No
No

k=1k=1 のとき、例えば小鳥は頂点 11 に舞い降り、1231\rightarrow 2\rightarrow 3 と移動することにより集めた整数は 1,2,31,2,3 です。その中で素数は 2,32,322 種類なので、このときの質問の答えは Yes です。
k=4k=4 のとき、どの頂点に舞い降りたとしても素数を 44 種類集めることはできません。

入力例2
4 0
10000 10002 10004 10006
出力例2
Yes
No
No
No
No

辺が存在しないことがあることに注意してください。

Submit


Go (1.21)