World Finals | ICPC 2023 Luxor 46th Annual hosted by ICPC World Championship AASTMT Problem R Zoo Management Time limit: 5 seconds 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. The way you move animals is by using special tunnels that con- A picture of a zoo with a camel, a donkey and (part of) a goat. nect the enclosures — you do not want the animals to move out- side, 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). So, 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 the part of the same move, and no tunnel is used more than once as a 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? Input The first line of the input consists of two integers n (1 ≤ n ≤ 4 · 105 ) and m (0 ≤ m ≤ 4 · 105 ), indicating the number of enclosures and tunnels. Then follow n lines, the ith of which contains two integers bi (1 ≤ bi ≤ 106 ) and ei (1 ≤ e ≤ 106 ), 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 e1 , . . . , en is a permutation of b1 , . . . , bn . Then 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. Output If it is possible to move the animals so that every enclosure contains the desired animal type, output possible. Otherwise, output impossible. 46th ICPC World Championship Problem R: Zoo Management © ICPC Foundation 5 World Finals | ICPC 2023 Luxor 46th Annual hosted by ICPC World Championship AASTMT Sample Input 1 Sample Output 1 3 3 possible 1 4 4 7 7 1 1 2 2 3 1 3 Sample Input 2 Sample Output 2 2 1 impossible 1 2 2 1 1 2 Sample Input 3 Sample Output 3 5 6 possible 10 40 20 30 30 50 40 20 50 10 1 2 2 3 1 3 3 4 3 5 4 5 Sample Input 4 Sample Output 4 4 4 impossible 10 10 10 20 20 10 20 20 1 2 2 3 3 4 1 4 46th ICPC World Championship Problem R: Zoo Management © ICPC Foundation 6