Zoo Management

When managing a zoo, you sometimes want to move animals between enclosures. For example, the zebras may like the spacier enclosure currently occupied by the penguins, the penguins may want to move to the colder enclosure where the koalas live, and the koalas will move to an empty enclosure filled with eucalyptus. You would move the koalas first to free the colder enclosure, then move the penguins there, and finally move the zebras.

Animals move through special tunnels that connect the enclosures. They must never go outside, because they may get scared or run away and hurt themselves.

Now every enclosure is full, which makes moving animals much harder. For example, if the koalas had to move into the former zebra enclosure, no animal could move first. Instead, the animals move at the same time. The zebras, koalas, and penguins start down different tunnels together and arrive at their new enclosures together, so they never meet. You cannot simply swap the animals in two connected enclosures, because they would meet in the tunnel and become scared.

You can, any number of times, choose a set of animals and move each one to an adjacent enclosure through a tunnel, as long as the animal in that enclosure also moves in the same move. No tunnel may be used more than once in the same move. Is it possible to reach the desired arrangement in a series of moves?

The first line contains two integers $n$ ($1 \le n \le 4 \cdot 10^5$) and $m$ ($0 \le m \le 4 \cdot 10^5$), the number of enclosures and tunnels. The next $n$ lines each contain two integers $b_i$ ($1 \le b_i \le 10^6$) and $e_i$ ($1 \le e_i \le 10^6$), the type of animal in enclosure $i$ at the start and the type of animal you want in enclosure $i$ after all moves. It is guaranteed that $e_1, \dots, e_n$ is a permutation of $b_1, \dots, b_n$. The next $m$ lines each contain two integers $x$ and $y$ ($1 \le x < y \le n$), meaning enclosures $x$ and $y$ are connected by a two-way tunnel. No two enclosures are connected by more than one tunnel.

If it is possible to move the animals so that every enclosure contains the desired animal type, print possible. Otherwise, print impossible.