Hái Hoa

Nông trại của Bác John là một đồ thị vô hướng liên thông gồm $N$ đỉnh và $M$ cạnh không trọng số. Bác John bắt đầu tại đỉnh $1$.

Ban đầu, $K$ đỉnh $s_1,\dots ,s_K$ có vườn hoa và $L$ đỉnh $d_1,\dots ,d_L$ là đích đến.

Một đường đi từ đỉnh $1$ đến đích $x$ được gọi là đẹp nếu:

• Đó là đường đi ngắn nhất từ $1$ đến $x$
• Bác John đi qua tất cả các vườn hoa trên đường đi

Bác John có thể tạm thời thêm một vườn hoa tại đỉnh $f$ ($2\le f\le N$). Với mỗi đỉnh $f$ từ $2$ đến $N$, xác định liệu có tồn tại đường đi đẹp sau khi thêm vườn hoa tại $f$ hay không.

Dữ liệu vào

• Dòng 1: Số nguyên $T$ — số bộ test ($1\le T\le 100$)
• Với mỗi bộ test:
  • Dòng 1: Bốn số nguyên $N,M,K,L$
  • Dòng 2: $K$ số nguyên $s_1,\dots ,s_K$ (bỏ trống nếu $K=0$)
  • Dòng 3: $L$ số nguyên $d_1,\dots ,d_L$
  • $M$ dòng tiếp theo: Hai số nguyên $u,v$ mô tả cạnh

Tổng $N$ và $M$ trên tất cả bộ test không vượt quá ${10}^6$.

Dữ liệu ra

Với mỗi bộ test, in chuỗi nhị phân độ dài $N-1$: ký tự thứ $i$ là 1 nếu đỉnh $i+1$ thỏa mãn, 0 nếu không.

Ràng buộc

• $2\le N\le 2\times {10}^5$
• $N-1\le M\le 2\times {10}^5$
• $0\le K\le N-1$, $1\le L\le N-1$

Ví dụ

Ghi chú

• Test 2-5: $K=0$ hoặc $L=1$
• Test 6-10: $K\le 1$
• Test 11-23: Không ràng buộc bổ sung