Colored Sticks

Time limit2sMemory limit128 MB

Summary
Given colored-end sticks, decide if they can all be joined into one line where touching ends share the same color, which reduces to checking an Eulerian path exists.
Level

Medium6 of 10

Topics
Union-find, Graph, String, Hash map
Solved
No attempts yet

Problem

You are given wooden sticks whose two ends are colored. Determine whether all sticks can be arranged in one straight line so that whenever two stick ends touch, the colors on those two ends are the same. Every stick must be used exactly once.

Input

Input is given until EOF. Each line contains two lowercase English words separated by one space; they are the colors on the two ends of one stick. Each color name has length at most 10. The number of sticks is at most 250,000.

Output

Print Possible if all sticks can be arranged in one valid line. Otherwise, print Impossible.

Examples1

  1. Example 1

    Input
    blue red
red violet
cyan blue
blue magenta
magenta cyan
    Expected output
    Possible