Custodial Cleanup

Farmer John quản lý một khách sạn với $N$ chuồng và $M$ hành lang. Mỗi chuồng $i$ có màu $C_i$ và ban đầu chứa một chìa khóa màu $S_i$. FJ phải sắp xếp lại chìa khóa sao cho chuồng $i$ chứa chìa khóa màu $F_i$, bắt đầu và kết thúc tại chuồng 1.

Quy tắc di chuyển:

• FJ có thể nhặt hoặc đặt chìa khóa
• FJ có thể vào chuồng 1 tự do qua hành lang
• FJ chỉ có thể vào chuồng khác nếu đang cầm chìa khóa cùng màu với chuồng đó

Dữ liệu vào

• Dòng 1: $T$ (số test case)
• Mỗi test case: dòng trống, rồi $N$, $M$; mảng $C$, $S$, $F$; $M$ cạnh

Dữ liệu ra

Với mỗi test case: "YES" hoặc "NO".

Ràng buộc

• $1\le T\le 100$, tổng $N\le {10}^5$, tổng $M\le 2\times {10}^5$
• $S$ là hoán vị của $F$

Ví dụ