커모드 곰의 연어 사냥

$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<v_i\le N)$ $i\ne j$이면 $(u_i,v_i)\ne(u_j,v_j)$이다.

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

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

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

첫 줄에 맛있는 연어를 먹는 곰을 출력한다. 흰곰이 먹으면 $0$, 흑곰이 먹으면 $1$을 출력한다.