#P1333. 瑞瑞的木棍

瑞瑞的木棍

题目描述

瑞瑞有一堆的玩具木棍,每根木棍的两端分别被染上了某种颜色,现在他突然有了一个想法,想要把这些木棍连在一起拼成一条线,并且使得木棍与木棍相接触的两端颜色都是相同的,给出每根木棍两端的颜色,请问是否存在满足要求的排列方式。

例如,如果只有 2 根木棍,第一根两端的颜色分别为 red, blue,第二根两端的颜色分别为 red, yellow,那么 blue---red | red----yellow 便是一种满足要求的排列方式。

输入格式

输入有若干行,每行包括两个单词,表示一根木棍两端的颜色,单词由小写字母组成,且单词长度不会超过 1010 个字母,最多有 250000250000 根木棍。

输出格式

如果木棒能够按要求排列,输出 Possible,否则输出 Impossible

blue red
red violet
cyan blue
blue magenta
magenta cyan
Possible