Vì sự thiếu tổ chức trong cấu trúc của hệ thống mootel (hệ thống nhà nghỉ mới nhưng ưu tiên các chú trâu/bò), nông dân John quyết định trở thành người bảo quản mootel nhằm khôi phục lại trật tự giữa các chuồng.

Mỗi mootel có \(N\) chuồng được đánh số từ \(1\) đến \(N\) \((1 \le N \le 10^5)\) và có \(M\) \((1 \le M \le 10^5)\) hành lang hai chiều nối giữa các cặp chuồng với nhau. Chuồng \(i\) được sơn màu \(C_i\) và ban đầu có một chiếc chìa khoá màu \(S_i\) ở bên trong. Bác John cần sắp xếp lại những chiếc chìa khoá này nhằm xoa dịu những chú bò và khôi phục lại trật tự giữa các chuồng.
Bác John bắt đầu ở chuồng \(1\), không cầm chiếc chìa khoá nào và được phép thực hiện một trong các hành động sau:

• Nhặt một chiếc chìa khoá trong chuồng mà hiện tại bác đang đứng. Bác John có thể giữ nhiều chìa khoá cùng lúc.
• Đặt một chiếc chìa khoá trong tay xuống chuồng hiện tại. Một chiếc chuồng có thể để nhiều chìa khoá.
• Trở về chuồng \(1\) thông qua các hành lang.
• Đi đến một chuồng khác chuồng \(1\) thông qua các hành lang. Bác John chỉ có thể đi đến các chuồng mà có màu trùng với màu của một chiếc chìa khoá mà bác John đang cầm trên tay.

Không may thay, dường như những chiếc chìa khoá đang không ở vị trí dự định của nó. Để khôi phục lại trật tự cho các mootel của mình, bác John cần đặt chiếc chìa khoá màu \(F_i\) bên trong chuồng thứ \(i\). Dữ liệu đảm bảo rằng \(S\) là một hoán vị của \(F\).

Cho \(T\) \((1 \le T \le 100)\) mootel khác nhau, bác John bắt đầu từ chuồng \(1\) và cần đặt những chiếc chìa khoá vào vị trí thích hợp của nó và kết thúc ở chuồng \(1\). Với mỗi mootel, kiểm tra xem liệu bác John có thể tái cấu trúc trật tự cho nó không.

Input

• Dòng đầu chứa số \(T\).
• Mỗi test sẽ cách nhau bởi một dòng trống. Dòng đầu tiên của mỗi test sẽ gồm hai số \(N, M\).
• Dòng thứ hai của mỗi test gồm \(N\) số \(C_i\) \((1 \le C_i \le N)\).
• Dòng thứ ba của mỗi test gồm \(N\) số \(S_i\) \((1 \le S_i \le N)\).
• Dòng thứ tư của mỗi test gồm \(N\) số \(F_i\) \((1 \le F_i \le N)\).
• \(M\) dòng tiếp theo của mỗi test sẽ gồm \(2\) số khác nhau \(u_i\) và \(v_i\) \((1 \le u_i, v_i \le N)\), nghĩa là có một hành lang hai chiều nối giữa chuồng \(u_i\) và chuồng \(v_i\). Không có hai hành lang nào giống nhau.

Tổng của \(N\) giữa các test không quá \(10^5\), tổng của \(M\) giữa các test không quá \(2 \times 10^5\).

Output

• Gồm \(T\) dòng, mỗi dòng ghi chữ "YES" hoặc "NO" (không bao gồm dấu nháy kép) cho biết bác John có thể đặt lại các chìa khoá màu \(F_i\) vào chuồng \(i\) hay không.

Scoring

• Subtask \(1\): \(N, M \le 8\).
• Subtask \(2\): \(C_i = F_i\) \(\forall i \in [1, n]\).
• Subtask \(3\): Không có ràng buộc gì thêm.

2

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

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

YES
NO

- Chuồng hiện tại: $1$. Chìa khoá đang cầm: []. Chìa khoá trong chuồng: [3, 4, 3, 4, 2].
(nhặt chìa khoá màu $3$).
- Chuồng hiện tại: $1$. Chìa khoá đang cầm: [3]. Chìa khoá trong chuồng: [x, 4, 3, 4, 2].
(di chuyển từ chuồng $1 \rightarrow 2$, bước đi này hợp lệ vì đang có chìa khoá màu $C_2 = 3$).
- Chuồng hiện tại: $2$. Chìa khoá đang cầm: [3]. Chìa khoá trong chuồng: [x, 4, 3, 4, 2].
(nhặt chìa khoá màu $4$).
- Chuồng hiện tại: $2$. Chìa khoá đang cầm: [3, 4]. Chìa khoá trong chuồng: [x, x, 3, 4, 2].
(di chuyển từ chuồng $2 \rightarrow 1 \rightarrow 4 \rightarrow 5$, hợp lệ vì đang có chìa khoá màu $C_4 = 4$ và $C_5 = 3$).
- Chuồng hiện tại: $5$. Chìa khoá đang cầm: [3, 4]. Chìa khoá trong chuồng: [x, x, 3, 4, 2].
(nhặt chìa khoá màu $2$ và đặt chìa khoá màu $3$ xuống).
- Chuồng hiện tại: $5$. Chìa khoá đang cầm: [2, 4]. Chìa khoá trong chuồng: [x, x, 3, 4, 3].
(di chuyển từ chuồng $5 \rightarrow 4 \rightarrow 1 \rightarrow 3$, hợp lệ vì đang có chìa khoá màu $C_4 = 4$ và $C_3 = 2$).
- Chuồng hiện tại: $3$. Chìa khoá đang cầm: [2, 4]. Chìa khoá trong chuồng: [x, x, 3, 4, 3].
(nhặt chìa khoá màu $3$ và đặt chìa khoá màu $4$ xuống).
- Chuồng hiện tại: $3$. Chìa khoá đang cầm: [2, 3]. Chìa khoá trong chuồng: [x, x, 4, 4, 3].
(di chuyển từ chuồng $3 \rightarrow 2$ và đặt chìa khoá màu $3$ xuống).
- Chuồng hiện tại: $2$. Chìa khoá đang cầm: [2]. Chìa khoá trong chuồng: [x, 3, 4, 4, 3].
(di chuyển từ chuồng $2 \rightarrow 1$ và đặt chìa khoá màu $2$ xuống).
- Chuồng hiện tại: $1$. Chìa khoá đang cầm: []. Chìa khoá trong chuồng: [2, 3, 4, 4, 3].

5

2 0
1 2
2 2
2 2

2 1
1 1
2 1
2 1
1 2

2 1
1 1
2 1
1 2
1 2

2 1
1 1
1 2
2 1
1 2

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

YES
YES
NO
YES
NO