P1333 Ruirui's Sticks

Ruirui has a pile of toy sticks. Each stick has a color painted on each end. He suddenly has an idea: he wants to connect these sticks end to end to form a single line, such that the colors on the touching ends of adjacent sticks are the same. Given the colors on both ends of each stick, determine whether there exists an arrangement that meets this requirement. For example, if there are only $2$ sticks, the first stick has colors `red` and `blue` on its ends, and the second stick has colors `red` and `yellow` on its ends, then `blue --- red | red --- yellow` is a valid arrangement.

The input consists of multiple lines. Each line contains two words representing the colors on the two ends of a stick. Each word consists of lowercase letters, and the length of each word does not exceed $10$ letters. There are at most $250000$ sticks.

If the sticks can be arranged as required, output `Possible`; otherwise, output `Impossible`.

Translated by ChatGPT 5