{"kind":"task","effective_mode":"full","benchmark":{"kind":"benchmark","effective_mode":"full","slug":"hlce","formal_name":"Humanity's Last Code Exam","introduction":"Humanity's Last Code Exam evaluates problem solving and code generation using ICPC World Finals and IOI problems. The project describes 235 problems; this import selects its public ICPC dataset of 146 problems.","introduction_ja":"","introduction_en":"","category":"Category not supplied","task_count":null,"acquisition_status":"Acquisition status not supplied","official_url":"https://humanity-s-last-code-exam.github.io/website/","indexing_mode":"noindex","profile":{"resources":[],"task_format":"","scoring":"","metric":"","size":"","answer_access":"","license":"","citation":"","maintainer":"","released":"","why_hard":"","related":[]}},"task_id":"ee46a079-cead-5c94-828a-3e06802fba8d","task_key":"ICPC~2dWorld~2dFinals--examples--2022~5fR","task_revision_id":"3","upstream_id":"2022_R","short_description":"Zoo Management","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"When managing a zoo, you sometimes want to move the animals between enclosures. You might figure out that the zebras will enjoy the spacier enclosure currently occupied by the penguins, while the penguins might want to move to the colder enclosure where the koalas currently live; and koalas will move to an empty enclosure that can be filled up with eucalyptus. So, you would move the koalas first, to free up the colder enclosure, then move the penguins there, and finally move the zebras.\\n\\nThe way you move animals is by using special tunnels that connect the enclosures — you do not want the animals to move outside, both because of the risk that they will be scared, and because of the risk that they might run away and hurt themselves. Unfortunately, you have acquired more animals recently, and all the enclosures are now full, which makes moving animals around much harder. Imagine, for instance, that the koalas were to move to the former zebra enclosure — you cannot move any set of animals first. Instead, what you learned to do, is to move the animals at the same time — the zebras, koalas, and penguins start moving down different tunnels at the same time, and arrive at their new enclosures at the same time—and thus they never meet. Note that you cannot just swap the animals in two connected enclosures this way (because they would meet in the tunnel and become scared).\\n\\nSo, now you have a puzzle. You have a list of enclosures, each with an animal type inside; some of those enclosures are connected by tunnels. You can, any number of times, choose some set of animals and move each one to an enclosure adjacent by tunnel, as long as the animal in that enclosure is also moved as part of the same move, and no tunnel is used more than once as part of the same move. You also have your vision of the perfect way to position the animals. Is it possible to do so, in a series of moves?\\n\\n### Input\\n\\nThe first line of the input consists of two integers \\\\( n \\\\) (1 ≤ \\\\( n \\\\) ≤ 4 × \\\\( 10^5 \\\\)) and \\\\( m \\\\) (0 ≤ \\\\( m \\\\) ≤ 4 × \\\\( 10^5 \\\\)), indicating the number of enclosures and tunnels. Then follow \\\\( n \\\\) lines, the \\\\( i \\\\)-th of which contains two integers \\\\( b_i \\\\) (1 ≤ \\\\( b_i \\\\) ≤ \\\\( 10^6 \\\\)) and \\\\( e_i \\\\) (1 ≤ \\\\( e_i \\\\) ≤ \\\\( 10^6 \\\\)), indicating the type of animal that is in enclosure \\\\( i \\\\) at the beginning, and the type of animal that you want to be in enclosure \\\\( i \\\\) after all the moves. You may assume that \\\\( e_1, \\\\ldots, e_n \\\\) is a permutation of \\\\( b_1, \\\\ldots, b_n \\\\).\\n\\nThen follow \\\\( m \\\\) lines describing the tunnels. Each line contains two integers \\\\( x \\\\) and \\\\( y \\\\) (1 ≤ \\\\( x < y \\\\) ≤ \\\\( n \\\\)), indicating that enclosures \\\\( x \\\\) and \\\\( y \\\\) are connected by a two-way tunnel. No two enclosures are connected by more than one tunnel.\\n\\n### Output\\n\\nIf it is possible to move the animals so that every enclosure contains the desired animal type, output `possible`. Otherwise, output `impossible`.\\n\\n### Sample Input 1\\n```\\n3 3\\n1 4\\n4 7\\n7 1\\n1 2\\n2 3\\n1 3\\n```\\n\\n### Sample Output 1\\n```\\npossible\\n```\\n\\n### Sample Input 2\\n```\\n2 1\\n1 2\\n2 1\\n1 2\\n```\\n\\n### Sample Output 2\\n```\\nimpossible\\n```\\n\\n### Sample Input 3\\n```\\n5 6\\n10 40\\n20 30\\n30 50\\n40 20\\n50 10\\n1 2\\n2 3\\n1 3\\n3 4\\n3 5\\n4 5\\n```\\n\\n### Sample Output 3\\n```\\npossible\\n```\\n\\n### Sample Input 4\\n```\\n4 4\\n10 10\\n10 20\\n20 10\\n20 20\\n1 2\\n2 3\\n3 4\\n1 4\\n```\\n\\n### Sample Output 4\\n```\\nimpossible\\n```\",\"question_title\":\"Zoo Management\"}","display_format":"text","language":"","answer_status":"published","assets":[],"source_url":"https://humanity-s-last-code-exam.github.io/website/","history":"initial import","indexing_mode":"noindex","subproblems":[],"grids":[]}