Ở một trường vẽ nào đó bên Áo, bạn H đang làm một bài kiểm tra đầu vào để vào trường. Trải qua rất nhiều thử thách vẽ, cuối cùng bạn phải đối mặt với thử thách cuối cùng là liên quan tới tư duy. Bạn được cho một đồ thị vô hướng ~N~ đỉnh ~M~ cạnh và hai dãy ~A~ và ~B~. Bạn đó có thể gán ~A_u := \min(A_u, A_v)~ nếu có cạnh giữa ~u~ và ~v~. Liệu có thể biến đổi mảng ~A~ thành mảng ~B~ hay không? Thử thách này rất khó nên bạn H nhờ các bạn giải giúp để hi vọng được đỗ vào ngành mà bạn mong muốn.

Input

Dữ liệu vào từ file văn bản artschool.inp:

Dòng đầu ghi một số nguyên dương ~T~ là số lượng trường hợp test.

Mỗi nhóm dòng trong số ~T~ nhóm dòng tiếp theo mô tả một trường hợp test có cấu trúc như sau:

• Dòng thứ nhất gồm hai số nguyên dương ~N~ và ~M~ ~(1 \leq N \leq 150000, 1 \leq M \leq 200000)~.

• Dòng thứ hai gồm ~n~ số nguyên dương ~A_i~ ~(1 \leq A_i \leq N)~.

• Dòng thứ ba gồm ~n~ số nguyên dương ~B_i~ ~(1 \leq B_i \leq N)~.

• Dòng thứ ~i~ trong số ~M~ dòng tiếp theo gồm hai số nguyên dương ~u_i, v_i~ thể hiện có cạnh nối giữa hai đỉnh ~u_i~ và ~v_i~ ~(1\leq u_i, v_i \leq N)~.

Gọi ~\sum{N}~ và ~\sum{M}~ tương ứng là tổng của tất cả các giá trị ~N~ và ~M~ trong tất cả ~T~ trường hợp test. Dữ liệu đảm bảo ~\sum{N} \leq 3\times 10^5~ và ~\sum{M} \leq 4 \times 10^5~.

Output

Ghi ra file văn bản artschool.out gồm ~T~ dòng, mỗi dòng là đáp án của một test. Nếu trong test thứ ~i~, bạn H có thể biến đổi mảng sao cho thỏa mãn điều kiện, in ra dòng thứ ~i~ là ~1~, ngược lại in ra ~0~.

Scoring

Sample Input 1

2
2 1
1 2
1 2
1 2
3 1
1 2 3
3 2 1
1 3

Sample Output 1

1
0

Sample Input 2

1
3 2
3 2 1
1 1 1
1 2
2 3

Sample Output 2

1

Notes

Ở ví dụ 1, test 1, dãy A đã bằng dãy B sẵn từ đâu nên đáp án là ~1~.

Ở ví dụ 1, test 2, ta không có cách nào biến ~A_1 = B_1~ nên đáp án là ~0~.

Ở ví dụ 2, ta dùng 2 phép gán lần lượt ~A_2= min(A_2, A_3)~, ~A_1= min(A_1, A_2)~, dãy ~A~ sẽ trở thành dãy ~B~. Đáp án là ~1~