Custodial Cleanup

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \leq T \leq 100$ , tổng $N \leq 10^{5}$ , tổng $M \leq 2 \times 10^{5}$
$S$ là hoán vị của $F$

Ví dụ

Input	Output	Giải thích
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	Test 1: có thể sắp xếp lại. Test 2: không thể.

Bình luận

Không có bình luận tại thời điểm này.