Quản lý sở thú
Đề bài
Mô tả
Khi quản lý một sở thú, đôi khi bạn muốn chuyển các con vật giữa các chuồng. Có thể bạn nhận ra rằng bầy ngựa vằn sẽ thích chuồng rộng rãi hơn mà bầy chim cánh cụt đang ở, còn bầy chim cánh cụt lại muốn chuyển sang chuồng lạnh hơn nơi bầy gấu koala đang sống; và bầy koala sẽ chuyển sang một chuồng trống có thể trồng đầy cây bạch đàn. Vậy bạn sẽ chuyển bầy koala trước để giải phóng chuồng lạnh hơn, rồi chuyển bầy chim cánh cụt vào đó, cuối cùng chuyển bầy ngựa vằn.
Cách bạn chuyển các con vật là dùng những đường hầm đặc biệt nối các chuồng với nhau: bạn không muốn các con vật đi ra ngoài, vừa vì chúng có thể hoảng sợ, vừa vì chúng có thể bỏ chạy và tự làm mình bị thương.
Không may, gần đây bạn nhận thêm nhiều con vật, và giờ mọi chuồng đều đã đầy, khiến việc chuyển các con vật khó hơn nhiều. Chẳng hạn, nếu bầy koala phải chuyển vào chuồng cũ của bầy ngựa vằn thì bạn không thể chuyển bầy nào trước được. Thay vào đó, bạn học được cách chuyển các con vật cùng một lúc: bầy ngựa vằn, bầy koala và bầy chim cánh cụt bắt đầu đi vào các đường hầm khác nhau cùng một lúc và tới chuồng mới cùng một lúc, nhờ vậy chúng không bao giờ gặp nhau. Lưu ý rằng theo cách này bạn không thể đơn giản đổi chỗ các con vật ở hai chuồng được nối với nhau (vì chúng sẽ gặp nhau trong đường hầm và hoảng sợ).
Vậy bạn có một câu đố. Bạn có danh sách các chuồng, mỗi chuồng có một loài vật bên trong; một số cặp chuồng được nối với nhau bằng đường hầm. Bạn có thể thực hiện bao nhiêu lần cũng được thao tác sau: chọn một tập các con vật và chuyển mỗi con sang một chuồng kề với chuồng của nó qua một đường hầm, với điều kiện con vật trong chuồng đích cũng được chuyển đi trong cùng thao tác đó, và không có đường hầm nào được dùng quá một lần trong cùng một thao tác. Bạn cũng có hình dung về cách sắp xếp hoàn hảo các con vật. Hỏi có thể đạt được cách sắp xếp đó bằng một dãy thao tác hay không?
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên và : số chuồng và số đường hầm.
- dòng tiếp theo, dòng thứ gồm hai số nguyên và : loài vật ở chuồng lúc đầu, và loài vật bạn muốn có ở chuồng sau mọi thao tác. Dãy là một hoán vị của dãy .
- dòng tiếp theo mô tả các đường hầm, mỗi dòng gồm hai số nguyên và (), cho biết chuồng và chuồng được nối bằng một đường hầm hai chiều. Không có hai chuồng nào được nối bởi nhiều hơn một đường hầm.
Dữ liệu ra
Nếu có thể chuyển các con vật để mọi chuồng đều chứa đúng loài vật mong muốn, in ra possible. Ngược lại, in ra impossible.
Ràng buộc
- , .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 1 4 4 7 7 1 1 2 2 3 1 3 |
possible | Trong một thao tác, chuyển cùng lúc con vật ở chuồng sang chuồng , ở chuồng sang chuồng và ở chuồng sang chuồng . |
| 2 1 1 2 2 1 1 2 |
impossible | Cần đổi chỗ hai con vật qua cùng một đường hầm, điều này bị cấm. |
| 5 6 10 40 20 30 30 50 40 20 50 10 1 2 2 3 1 3 3 4 3 5 4 5 |
possible | Hai vòng tam giác và chung chuồng . |
| 4 4 10 10 10 20 20 10 20 20 1 2 2 3 3 4 1 4 |
impossible | Các chuồng tạo thành một vòng ; mỗi thao tác chỉ có thể xoay các con vật quanh vòng này, nên không bao giờ đạt được thứ tự . |
Bình luận