問題一覧 > 通常問題

No.1805 Approaching Many Typhoon

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 64
作問者 : matcharate12matcharate12 / テスター : Namu3Namu3
0 ProblemId : 6958 / 自分の提出
問題文最終更新日: 2022-04-01 11:33:56

※問題の不備の修正について

1/12 20:58 テストケースに不備が見つかりましたので、修正が終わり次第リジャッジします。申し訳ございませんでした。
また問題文とケースが矛盾しているところがありました。問題文が間違っていたので修正します。
1/12 21:12 リジャッジが完了しました。また問題文を修正しました。申し訳ございませんでした。
1/12 21:45 問題文の制約と矛盾しているケースがありました。リジャッジを行いました。
1/12 22:10 問題文を改正しました。
1/13 15:31 質問があったので、その内容をもとに問題文を改正しました。
1/16 16:58 質問から問題文に不備が見つかりましたので訂正しました。申し訳ありませんでした。

問題文

小さい島、ここyuki島にはmatcharate君が住んでいます。ここの付近の海域では $N$ 島の島と、$M$ 便の船があります。
それぞれ島には $1,2,3,...N$ の番号が付けられており、$i\ (1≦i≦M)$ 番目の便は島 $F_i$ と島 $T_i$ の $2$ つの島の間で行き来できる船が用意されています。

...ところが今日の夜、$U$ 個の台風が近づいていて、明日になる前に $j\ (1≦j≦U)$ 番目の島 $I_j$ を経由することは危険だと判断し、その島を閉鎖することになってしまいました。
そして夜が更け、出発することになりました。matcharate君は島 $I_j$ を経由せずに島 $S$ から島 $G$ に到着することはできるでしょうか？

入力

$N\ M$
$S\ G$
$F_1\ T_1$
$F_2\ T_2$
$:$
$F_M\ T_M$
$U$
$I_1\ I_2\ …\ I_U$
・$2≦N≦2000$
・$1≦S≠G≦N$
・$1≦M≦min(\frac{N(N-1)}{2},2000)$
・$1≦F_i≠T_i≦N$
・$0≦U≦500$
・$1≦I_j≦N$、$I_j≠S$、$I_j≠G$

・追記: 1/12 21:12 $U$ の制約を間違えておりました。申し訳ございませんでした。$U=0$ になりうることにも注意してください。

出力

可能なら

Yes
を、不可能なら 
No
と出力してください。

サンプル

サンプル1
入力
3 3
1 2
1 3
3 2
1 2
1
3
出力
Yes

島 $3$ は台風が近づいていて危険です。この場合、島 $1$ から島 $2$ に到着するための便が存在するのでたどり着くことができます。

サンプル2
入力
5 6
1 5
1 3
1 4
1 2
2 4
2 3
5 4
2
2 4
出力
No

島 $2,4$ が閉鎖しています。島 $5$ からは島 $4$ の便だけです。この場合は島 $4$ を経由する必要があるので、たどり着くことはできません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。