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é ghen tị với bé và rất quý bé , thì có nguy cơ nghịch ngợm và để lại món quà bất ngờ trong phòng kính thiên văn khi vào phòng sau , đồng thời vào phòng trước hoặc sau .
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 (): số bé trong nhóm. Các bé được đánh số từ đến theo thứ tự độ ngầu giảm dần.
Mỗi dòng trong dòng tiếp theo mô tả một bé. Dòng thứ chứa hai số nguyên và : là số hiệu bé mà bé thứ ghen tị, là số hiệu bé mà bé thứ rất, rất quý. Biết , , , , và với mọi trừ .
Dữ liệu ra
In ra một dòng gồm 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
- .
- , , , .
- với mọi .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 2 1 4 2 4 2 1 |
1 2 3 4 | Bé ghen tị với bé vào sau mình, nhưng bé mà bé quý vào giữa hai bé nên bé không nghịch. Các bé đều vào sau bé mình ghen tị. |
| 4 2 3 1 4 2 1 1 2 |
impossible | Bé và bé 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é vào trước bé thì bé (bé quý) phải vào giữa, nhưng bé ghen tị với bé và quý bé nên sẽ nghịch. Trường hợp bé vào trước bé tương tự với bé . |
Bình luận