25914번 - 커모드 곰의 연어 사냥

문제

$N$개의 정점과 $M$개의 간선으로 이루어진 그래프 $G$가 주어진다. 정점에는 1ドル$부터 $N$까지 번호가 매겨져 있고 그 중 $K$개의 정점에는 연어가 놓여 있다. $i$번 간선은 정점 $u_i$와 정점 $v_i$를 양방향으로 연결한다.

연어가 놓여 있는 정점 $u$에 대해 $S_u$를 다음 조건을 모두 만족하는 정점 $v$의 집합으로 정의한다.

• 정점 $v$에는 연어가 놓여 있지 않다.
• 정점 $u$와 정점 $v$를 연결하는 단순경로는 유일하게 존재한다.

단순경로는 중복되는 정점이 없는 경로이다. 정점 $u$에는 연어가 있어야 하고 정점 $v$에는 연어가 없어야 하지만 경로에 포함된 나머지 정점에는 연어가 있어도 되고 없어도 된다.

흰곰과 흑곰이 게임을 한다. 두 곰은 번갈아 가면서 게임을 하고 자신의 차례가 되면 다음과 같이 행동한다.

1. 연어가 놓여 있는 정점 $u$를 하나 선택한다.
2. $S_u$에서 정점을 하나 이상 선택하고 선택한 정점들에 연어를 올려놓는다.

더 이상 정점에 연어를 놓을 수 없을 때 게임을 종료한다. 연어가 부족해서 정점에 연어를 놓지 못하는 일은 생기지 않는다. 자신의 차례에 연어를 놓지 못한 곰은 다른 곰에게 맛있는 연어를 주고 자신은 맛없는 연어를 먹는다.

두 곰 모두 맛있는 연어를 먹고 싶기 때문에 항상 최선의 선택을 한다. 어떤 곰이 맛있는 연어를 먹는지 구해보자.

입력

첫 번째 줄에 정점의 개수 $N,ドル 간선의 개수 $M,ドル 연어가 놓여 있는 정점의 개수 $K$가 공백으로 구분되어 주어진다. $(2\le N\le 2\times 10^5;$ 1ドル\le M\le\min\left( {N\choose 2} ,2\times 10^5 \right) ;$ 1ドル\le K\le N)$

다음 $M$개의 줄에 간선의 정보 $u_i,v_i$가 공백으로 구분되어 주어진다. $(1\le u_i\lt v_i\le N)$ $i\neq j$이면 $\left( u_i,v_i \right)\neq\left( u_j,v_j \right)$이다.

다음 $K$개의 줄에 연어가 놓인 정점 $x_i$가 주어진다. $(1\le x_i\le N)$ $i\neq j$이면 $x_i\neq x_j$이다.

마지막 줄에는 게임을 먼저 시작하는 곰을 나타내는 정수 $c$가 주어진다. $(c\in\{0,1\})$ $c=0$이면 흰곰이 먼저 시작하고 $c=1$이면 흑곰이 먼저 시작한다.

입력으로 주어지는 모든 수는 정수이다.

출력

첫 번째 줄에 어떤 곰이 맛있는 연어를 먹는지 출력한다. 흰곰이 맛있는 연어를 먹으면 0ドル$을 출력하고 흑곰이 맛있는 연어를 먹으면 1ドル$을 출력한다.

제한

힌트