Description

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.

Input Format

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.

Output Format

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

blue red
red violet
cyan blue
blue magenta
magenta cyan

Possible

Hint

Translated by ChatGPT 5