trang chủ / đề bài / icpcwf24_g

Nhà trẻ

Đề bài

Mô tả

Đưa một nhóm trẻ mẫu giáo đi thăm cung thiên văn không hề dễ dàng. Bạn thật sự muốn làm điều này để mọi bé đều có cơ hội vào căn phòng có chiếc kính thiên văn khổng lồ và ngắm Sao Mộc. Nhưng giờ, khi sắp đi, bạn chợt nhớ đến những câu chuyện của các cô trông trẻ khác: các bé có thể nghịch ngợm và để lại vài "món quà bất ngờ" khó chịu trong phòng kính thiên văn cho những bé vào sau. Bạn rất muốn tránh điều đó.

Bạn hiểu rất rõ các bé trong nhóm. Mỗi bé ghen tị với một bé khác, ngầu hơn mình, và bé đó có thể nghịch ngợm trong phòng kính thiên văn nếu biết rằng bé mình ghen tị sẽ vào phòng vào một lúc nào đó sau mình (không nhất thiết ngay sau, chỉ cần ở một thời điểm nào đó về sau). Bạn tưởng việc này dễ: bé ngầu nhất lớp không có ai để ghen tị nên có thể vào đầu tiên, rồi các bé còn lại vào theo thứ tự độ ngầu. Tuy nhiên, bạn vừa biết rằng bé ngầu nhất là một ngoại lệ: thay vì ghen tị với ai đó ngầu hơn mình, bé ghen tị với một bé ngẫu nhiên nào đó trong nhóm. Nghe như một thảm họa!

May mắn là bạn cũng biết mỗi bé đều có một bé khác mà mình rất, rất quý. Vì vậy, mỗi khi một bé trong phòng kính thiên văn đang tính bày trò, nếu bé biết rằng bé mình quý sẽ vào phòng sau mình và trước bé mình ghen tị, bé sẽ kiềm chế không nghịch ngợm. Nói một cách chính xác: nếu bé A ghen tị với bé B và rất quý bé C, thì có nguy cơ A nghịch ngợm và để lại món quà bất ngờ trong phòng kính thiên văn khi B vào phòng sau A, đồng thời C vào phòng trước A hoặc sau B.

Bạn có thể tìm một thứ tự cho các bé vào phòng kính thiên văn sao cho không có món quà bất ngờ nào không?

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên n (3≤n≤200000): số bé trong nhóm. Các bé được đánh số từ 1 đến n theo thứ tự độ ngầu giảm dần.

Mỗi dòng trong n dòng tiếp theo mô tả một bé. Dòng thứ i chứa hai số nguyên ji và li: ji là số hiệu bé mà bé thứ i ghen tị, li là số hiệu bé mà bé thứ i rất, rất quý. Biết 1≤ji,li≤n, ji≠li, ji≠i, li≠i, và ji<i với mọi i trừ i=1.

Dữ liệu ra

In ra một dòng gồm n số nguyên: thứ tự các bé vào phòng kính thiên văn. Nếu có nhiều thứ tự thỏa mãn, in ra thứ tự bất kỳ. Nếu không tồn tại thứ tự nào, in ra impossible.

Ràng buộc

  • 3≤n≤200000.
  • 1≤ji,li≤n, ji≠li, ji≠i, li≠i.
  • ji<i với mọi 2≤i≤n.

Ví dụ

Input Output Giải thích
4
4 2
1 4
2 4
2 1
1 2 3 4 Bé 1 ghen tị với bé 4 vào sau mình, nhưng bé 2 mà bé 1 quý vào giữa hai bé nên bé 1 không nghịch. Các bé 2,3,4 đều vào sau bé mình ghen tị.
4
2 3
1 4
2 1
1 2
impossible Bé 1 và bé 2 ghen tị lẫn nhau nên một trong hai bé phải vào trước bé mình ghen tị. Nếu bé 1 vào trước bé 2 thì bé 3 (bé 1 quý) phải vào giữa, nhưng bé 3 ghen tị với bé 2 và quý bé 1 nên sẽ nghịch. Trường hợp bé 2 vào trước bé 1 tương tự với bé 4.

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