문제

가은이가 있는 충남대학교 캠퍼스는 $N$개의 지점과 이들을 잇는 $M$개의 도로로 이루어진 연결 무방향 그래프로 나타낼 수 있다. 모든 도로의 길이는 $1$이다. 가은이는 처음에 1번 지점에 있다.

초기에 $s_1, s_2, \ldots, s_K$번 지점에는 꽃밭이 있으며, $d_1, d_2, \ldots, d_L$번 지점은 목적지 지점이다. 가은이는 다음 조건을 모두 만족하는 경로를 예쁜 경로라고 부른다.

• 1번 지점에서 시작한다.
• 어떤 목적지 지점 $x$에서 끝난다.
• 1번 지점에서 $x$로 가는 최단 경로 중 하나이다.
• 모든 꽃밭 지점을 방문한다.

가은이는 마법의 지팡이를 휘둘러 최대 하나의 지점을 추가로 꽃밭으로 만들 수 있다. (이미 꽃밭인 지점을 다시 꽃밭으로 지정할 수도 있다.) 가은이는 $2$번부터 $N$번까지의 각 지점 $f$에 대해, $f$번 지점을 일시적으로 꽃밭으로 만들었을 때 예쁜 경로가 존재하는지 구하고자 한다.

여러 개의 테스트 케이스가 주어지며, 각 케이스는 독립적으로 처리해야 한다.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 100$)

각 테스트 케이스의 첫째 줄에 $N, M, K, L$이 공백으로 구분되어 주어진다. ($2 \le N \le 2 \cdot 10^5$; $N - 1 \le M \le 2 \cdot 10^5$; $0 \le K \le N - 1$; $1 \le L \le N - 1$)

둘째 줄에 꽃밭이 있는 각 지점의 번호 $s_1, s_2, \ldots, s_K$가 공백으로 구분되어 주어진다. ($2 \le s_i \le N$, $s_i$는 모두 서로 다름)

셋째 줄에 각 목적지 지점의 번호 $d_1, d_2, \ldots, d_L$이 공백으로 구분되어 주어진다. ($2 \le d_i \le N$, $d_i$는 모두 서로 다름)

이어지는 $M$개의 줄에 각 도로가 연결하는 두 지점 $u$와 $v$가 주어진다. 모든 도로는 가중치가 없는 무방향 간선이며, 모든 도로의 길이는 $1$로 같다. 다중 간선이나 자가 루프는 존재하지 않는다.

모든 테스트 케이스에 대해 $N$의 합과 $M$의 합은 각각 $10^6$을 넘지 않는다.

출력

각 테스트 케이스마다 길이가 $N - 1$인 이진 문자열을 한 줄에 출력한다. 문자열의 $i$번째 문자는 $(i+1)$번 지점을 꽃밭으로 만들었을 때 예쁜 경로가 존재하면 1, 그렇지 않으면 0이어야 한다.

예제 입력 1

1
7 7 0 1

5
1 2
2 3
3 4
4 5
5 6
6 7
3 6

예제 출력 1

111110

예제 입력 2

1
6 6 0 2

5 3
1 2
2 3
3 4
4 5
5 6
2 5

예제 출력 2

11010

예제 입력 3

3
4 3 2 1
2 3
4
1 2
2 3
3 4
4 4 2 1
2 3
4
1 2
1 3
2 4
3 4
5 5 2 1
2 4
5
1 2
1 3
2 4
3 4
4 5

예제 출력 3

111
000
1011

점수

• 테스트 케이스 4-6: $K = 0, L = 1$
• 테스트 케이스 7-9: $K = 0$
• 테스트 케이스 10-23: 추가적인 제약 조건이 없음.