Bracelet Crossings

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

Bessie tạo $N$ chiếc vòng tay, mỗi chiếc là một đường cong khép kín không tự cắt. Các vòng không cắt nhau. Sau khi bị xáo trộn, cô dùng $M$ tia sáng thẳng đứng để xác định thứ tự giao cắt.

Mỗi tia thẳng đứng thứ $j$ báo cáo danh sách $k_{j}$ màu theo thứ tự từ trên xuống. Mỗi màu xuất hiện đúng $0$ hoặc $2$ lần trong mỗi tia (vì vòng là đường khép kín). Không có tia nào đi qua đỉnh hoặc giao điểm đặc biệt.

Hãy xác định xem có tồn tại cấu hình vòng tay hợp lệ phù hợp với dữ liệu quan sát hay không.

Dữ liệu vào

Dòng $1$ : Số nguyên $T$ — số bộ test.
Với mỗi bộ test:
- Dòng $1$ : Hai số nguyên $N$ và $M$ .
- $M$ dòng tiếp: Mỗi dòng bắt đầu bằng $k_{j}$ , theo sau là $k_{j}$ số nguyên — màu các vòng từ trên xuống.

Dữ liệu ra

Với mỗi bộ test, in YES hoặc NO.

Ràng buộc

$1 \leq T \leq 50$ .
$1 \leq N \leq 50$ .
$1 \leq M \leq 50$ .
$0 \leq k_{j} \leq 2 N$ .

Ví dụ

Input	Output	Giải thích
5 1 2 2 1 1 2 1 1 1 3 2 1 1 0 2 1 1 2 1 4 1 2 1 2 4 2 6 1 2 2 3 3 1 6 1 2 4 4 2 1 2 2 4 1 1 2 2 4 2 2 1 1	YES NO NO YES NO	Test 2: vòng 1 phải liên tục nhưng tia giữa không có nó. Test 3: vòng 1 và 2 lồng vào nhau nên cắt nhau.

Bình luận

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