Lưu ý: Giới hạn thời gian của bài này là 3 giây, gấp 1,5 lần mức mặc định.

Cấu trúc trang trại của Farmer John có thể được biểu diễn bằng một đồ thị vô hướng liên thông gồm \(N\) đỉnh và \(M\) cạnh không trọng số (\(2\leq N\leq 2\cdot 10^5, N-1\leq M\leq 2\cdot 10^5\)). Ban đầu, Farmer John ở nhà kho của mình, được biểu diễn bởi trang trại \(1\).

Ban đầu, các trang trại \(s_1,s_2,\ldots,s_K\) có những cánh đồng hoa, còn các trang trại \(d_1,d_2,\ldots,d_L\) là các trang trại đích. FJ gọi một đường đi là đẹp nếu:

• Nó bắt đầu tại trang trại \(1\).
• Nó kết thúc tại một trang trại đích \(x\) nào đó.
• Không tồn tại đường đi nào ngắn hơn bắt đầu tại trang trại \(1\) và kết thúc tại trang trại \(x\).
• FJ ghé thăm tất cả các cánh đồng hoa trên đường đi.

FJ có thể vung đũa thần để làm cho nhiều nhất một trang trại nữa có một cánh đồng hoa (nếu trang trại đó chưa có). Tuy nhiên, FJ không giỏi quyết định cho lắm. Với mỗi trang trại \(f\) được đánh số từ \(2\) đến \(N\), sau khi FJ tạm thời làm cho trang trại \(f\) có một cánh đồng hoa, hãy xác định liệu có tồn tại một đường đi đẹp hay không.

Lưu ý rằng có nhiều bộ test và mỗi bộ test phải được xét độc lập.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\leq T\leq 100\)), số lượng bộ test độc lập.

Dòng đầu tiên của mỗi bộ test chứa \(N,M,K,L\) (\(0\leq K\leq N-1, 1\leq L\leq N-1\)).

Dòng tiếp theo chứa \(s_1,s_2,\ldots,s_K\) (\(2\leq s_i\leq N\) và các \(s_i\) đôi một khác nhau).

Dòng tiếp theo chứa \(d_1,d_2,\ldots,d_L\) (\(2\leq d_i\leq N\) và các \(d_i\) đôi một khác nhau).

\(M\) dòng tiếp theo, mỗi dòng chứa \(u\) và \(v\), biểu thị có một cạnh vô hướng nối trang trại \(u\) và trang trại \(v\). Mọi cạnh được xem là có cùng độ dài. Dữ liệu đảm bảo không có cạnh trùng hoặc khuyên.

Tổng \(N\) và tổng \(M\) trên tất cả các bộ test đều không vượt quá \(10^6\).

Dữ liệu ra

Với mỗi bộ test, in một xâu nhị phân có độ dài \(N-1\). Ký tự thứ \(i\) trong xâu phải là \(1\) nếu câu trả lời cho trang trại thứ \((i+1)\) là đúng.

Ví dụ

1
7 7 0 1

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

111110

1
6 6 0 2

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

11010

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

111
000
1011

Phân nhóm

• Inputs 4-6: \(K=0\) và \(L=1\).
• Inputs 7-9: \(K=0\).
• Inputs 10-23: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 Contest 3, Gold Division — bài gốc tiếng Anh “Picking Flowers”. Tác giả: Chongtian Ma. https://usaco.org/index.php?page=viewproblem2&cpid=1594