시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 31 7 7 36.842%

문제

상근이는 양 끝 부분이 칠해진 나무 막대 몇 개를 가지고 있다. 상근이는 문득 같은 색깔끼리 닿게 막대를 일직선으로 놓고 싶었다. 그것이 가능한지 불가능한지 알아보는 프로그램을 작성하시오.

입력

입력은 (막대의 개수)줄로 이루어져 있다. 두 단어가 있는데, 각 막대의 양 끝 부분의 색깔을 나타내고, 영어 소문자이며 최대 10자이다. 두 단어 사이에는 공백이 있다. 막대의 개수는 최대 25만 개이다.

출력

일직선으로 막대가 놓여질 수 있으면 Possible, 그렇지 않으면 Impossible을 출력한다.

예제 입력 1

blue red
red violet
cyan blue
blue magenta
magenta cyan

예제 출력 1

Possible
W3sicHJvYmxlbV9pZCI6IjE2OTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzkgXHViOWM5XHViMzAwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNTkxIFx1YjA1ZCBcdWJkODBcdWJkODRcdWM3NzQgXHVjZTYwXHVkNTc0XHVjOWM0IFx1YjA5OFx1YmIzNCBcdWI5YzlcdWIzMDAgXHViYTg3IFx1YWMxY1x1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYjM4XHViNGRkIFx1YWMxOVx1Yzc0MCBcdWMwYzlcdWFlNTRcdWIwN2NcdWI5YWMgXHViMmZmXHVhYzhjIFx1YjljOVx1YjMwMFx1Yjk3YyBcdWM3N2NcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHViMTkzXHVhY2UwIFx1YzJmNlx1YzVjOFx1YjJlNC4gXHVhZGY4XHVhYzgzXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1Y1x1YzljMCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NWNcdWM5YzAgXHVjNTRjXHVjNTQ0XHViY2Y0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgKFx1YjljOVx1YjMwMFx1Yzc1OCBcdWFjMWNcdWMyMTgpXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjNzg4XHViMjk0XHViMzcwLCBcdWFjMDEgXHViOWM5XHViMzAwXHVjNzU4IFx1YzU5MSBcdWIwNWQgXHViZDgwXHViZDg0XHVjNzU4IFx1YzBjOVx1YWU1NFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAsIFx1YzYwMVx1YzViNCBcdWMxOGNcdWJiMzhcdWM3OTBcdWM3NzRcdWJhNzAgXHVjZDVjXHViMzAwIDEwXHVjNzkwXHVjNzc0XHViMmU0LiBcdWI0NTAgXHViMmU4XHVjNWI0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWI5YzlcdWIzMDBcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1Y2Q1Y1x1YjMwMCAyNVx1YjljYyBcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzdjXHVjOWMxXHVjMTIwXHVjNzNjXHViODVjIFx1YjljOVx1YjMwMFx1YWMwMCBcdWIxOTNcdWM1ZWNcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCBQb3NzaWJsZSwgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCBJbXBvc3NpYmxlXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNjk2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29sb3JlZCBTdGlja3MiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYSBidW5jaCBvZiB3b29kZW4gc3RpY2tzLiBFYWNoIGVuZHBvaW50IG9mIGVhY2ggc3RpY2sgaXMgY29sb3JlZCB3aXRoIHNvbWUgY29sb3IuIElzIGl0IHBvc3NpYmxlIHRvIGFsaWduIHRoZSBzdGlja3MgaW4gYSBzdHJhaWdodCBsaW5lIHN1Y2ggdGhhdCB0aGUgY29sb3JzIG9mIHRoZSBlbmRwb2ludHMgdGhhdCB0b3VjaCBhcmUgb2YgdGhlIHNhbWUgY29sb3I/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBpcyBhIHNlcXVlbmNlIG9mIGxpbmVzLCBlYWNoIGxpbmUgY29udGFpbnMgdHdvIHdvcmRzLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLCBnaXZpbmcgdGhlIGNvbG9ycyBvZiB0aGUgZW5kcG9pbnRzIG9mIG9uZSBzdGljay4gQSB3b3JkIGlzIGEgc2VxdWVuY2Ugb2YgbG93ZXJjYXNlIGxldHRlcnMgbm8gbG9uZ2VyIHRoYW4gMTAgY2hhcmFjdGVycy4gVGhlcmUgaXMgbm8gbW9yZSB0aGFuIDI1MDAwMCBzdGlja3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SWYgdGhlIHN0aWNrcyBjYW4gYmUgYWxpZ25lZCBpbiB0aGUgZGVzaXJlZCB3YXksIG91dHB1dCBhIHNpbmdsZSBsaW5lIHNheWluZyBQb3NzaWJsZSwgb3RoZXJ3aXNlIG91dHB1dCBJbXBvc3NpYmxlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==