trang chủ / đề bài / icpcwf22_r

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 n và m: số chuồng và số đường hầm.
  • n dòng tiếp theo, dòng thứ i gồm hai số nguyên bi và ei: loài vật ở chuồng i lúc đầu, và loài vật bạn muốn có ở chuồng i sau mọi thao tác. Dãy e1,…,en là một hoán vị của dãy b1,…,bn.
  • m dòng tiếp theo mô tả các đường hầm, mỗi dòng gồm hai số nguyên x và y (1≤x<y≤n), cho biết chuồng x và chuồng y đượ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

  • 1≤n≤4·105, 0≤m≤4·105.
  • 1≤bi,ei≤106.

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 2 sang chuồng 1, ở chuồng 3 sang chuồng 2 và ở chuồng 1 sang chuồng 3.
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 1,2,3 và 3,4,5 chung chuồng 3.
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 1,2,3,4; 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ự 10,20,10,20.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0