Phá hoại công lý
Đề bài
Mô tả
The Shell là một nhà tù lớn, nơi các thành viên của Adwent từng bị giam giữ. Người ta nói rằng nó nằm ở đâu đó sâu dưới lòng đất của thế giới này, nhưng vị trí chính xác thì không ai biết.
Ở trung tâm của The Shell có phòng giam. Mỗi phòng giam được trang bị một camera giám sát cần được theo dõi liên tục. Có phòng giám sát, phòng giám sát thứ được kết nối với camera của một tập con xác định các phòng giam. Các phòng giám sát và các phòng giam được đánh số từ đến .
Vì lý do an ninh, mỗi phòng giám sát chỉ có thể theo dõi đúng một trong các camera mà nó được kết nối. The Shell được coi là an toàn khi và chỉ khi tồn tại một cách gán cho mỗi phòng giám sát một camera sao cho mọi camera đều được theo dõi. Đảm bảo rằng ban đầu The Shell an toàn.
Sau khi trốn thoát khỏi The Shell, các thành viên của Adwent lên kế hoạch phá hoại hệ thống an ninh của nó. Tuy nhiên, do nguồn lực có hạn, họ chỉ có thể thực hiện tối đa hành động phá hoại. Trong mỗi hành động, họ chọn một phòng giám sát và một phòng giam sao cho phòng giám sát hiện đang được kết nối với camera của phòng giam , rồi xóa kết nối đó.
Thủ lĩnh của Adwent muốn biết liệu có thể thực hiện một dãy gồm tối đa hành động phá hoại để The Shell không còn an toàn hay không. Nếu có thể, bạn cần in ra một dãy hành động hợp lệ.
Dữ liệu vào
Mỗi test gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu.
- Dòng đầu tiên chứa số nguyên (): số phòng giám sát và số phòng giam.
- Dòng thứ trong dòng tiếp theo chứa số nguyên (). nghĩa là phòng giám sát thứ được kết nối với camera của phòng giam thứ ; ngược lại .
Đảm bảo rằng The Shell an toàn ở cấu hình ban đầu.
Dữ liệu ra
Với mỗi bộ dữ liệu, nếu không thể làm The Shell mất an toàn bằng tối đa hành động phá hoại, in ra một số nguyên . Ngược lại, in ra:
- Dòng đầu tiên chứa số nguyên (): số hành động phá hoại.
- Dòng thứ trong dòng tiếp theo chứa hai số nguyên và (): chỉ số phòng giám sát và phòng giam được chọn ở hành động thứ . Kết nối giữa phòng giám sát và camera của phòng giam được chọn phải tồn tại trước khi thực hiện hành động.
Nếu có nhiều đáp án, bạn có thể in ra bất kỳ đáp án nào. Số hành động không cần nhỏ nhất.
Ràng buộc
- .
- , .
- Ban đầu tồn tại cách gán mỗi phòng giám sát một camera sao cho mọi camera đều được theo dõi.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 3 1 1 0 0 1 1 1 0 1 2 1 1 1 1 |
2 0 0 1 2 4 0 0 0 1 1 0 1 1 |
Bộ 1: ban đầu phòng 0 nối với camera 0, 1; phòng 1 nối với camera 1, 2; phòng 2 nối với camera 0, 2. Sau khi xóa kết nối (0, 0) và (1, 2), phòng 0 và phòng 1 đều chỉ còn nối với camera 1, nên không có cách gán nào để mọi camera được theo dõi. Bộ 2: số hành động không cần nhỏ nhất. |
| 3 1 1 2 1 0 0 1 3 1 1 1 1 1 1 1 1 1 |
1 0 0 1 0 0 3 0 0 0 1 0 2 |
Ví dụ bổ sung (không có trong đề gốc). Trong mỗi bộ, xóa mọi kết nối của phòng giám sát 0, khi đó phòng này không thể theo dõi camera nào. |
Bình luận