問題一覧 > 通常問題

No.1805 Approaching Many Typhoon

レベル : / AI推定難易度 : 500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 79
作問者 : matcharate12 / テスター : Namu3
お気に入りにしたユーザー ProblemId : 6958 / 自分の提出
問題文最終更新日: 2022-04-01 11:33:56
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

※Corrections to the Problem

1/12 20:58 A flaw was found in the test cases, so we will rejudge once the fix is complete. We apologize.
There was also a contradiction between the problem statement and the cases. The problem statement was wrong, so we will correct it.
1/12 21:12 The rejudge has been completed, and the problem statement has been corrected. We apologize.
1/12 21:45 There were cases that contradicted the constraints in the problem statement. A rejudge has been performed.
1/12 22:10 The problem statement has been revised.
1/13 15:31 We received a question, and the problem statement has been revised based on it.
1/16 16:58 A question revealed a flaw in the problem statement, so it has been corrected. We apologize.

Problem Statement

matcharate lives here on yuki Island, a small island. In the waters near here, there are $N$ islands and $M$ ship services.
The islands are numbered $1,2,3,...N$, and for the $i\ (1≦i≦M)$-th service, a ship is provided that can travel back and forth between the $2$ islands, island $F_i$ and island $T_i$.

...However, tonight $U$ typhoons are approaching, and it has been judged dangerous to pass through the $j\ (1≦j≦U)$-th island $I_j$ before tomorrow comes, so that island has ended up being closed.
Then the night deepened, and it is time to depart. Can matcharate arrive at island $G$ from island $S$ without passing through island $I_j$?

Input

$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$

・Addendum: 1/12 21:12 The constraint on $U$ was wrong. We apologize. Note also that $U=0$ is possible.

Output

If it is possible, print

Yes
and if it is impossible, print 
No
.

Sample

Sample 1
Input
3 3
1 2
1 3
3 2
1 2
1
3
Output
Yes

Island $3$ is dangerous because a typhoon is approaching. In this case, there is a service for getting from island $1$ to island $2$, so he can reach it.

Sample 2
Input
5 6
1 5
1 3
1 4
1 2
2 4
2 3
5 4
2
2 4
Output
No

Islands $2,4$ are closed. From island $5$, there is only the service to island $4$. In this case, he would have to pass through island $4$, so he cannot reach it.

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