색 막대
시간 제한2초메모리 제한128 MB
양끝에 색이 있는 막대들을 이어 붙였을 때 접하는 끝의 색이 항상 같도록 한 줄로 배열할 수 있는지 판별하는 문제로, 오일러 경로 존재 여부를 확인해야 합니다.
문제
상근이는 여러 개의 나무 막대를 가지고 있다. 각 막대의 양쪽 끝은 색이 칠해져 있다. 모든 막대를 한 줄로 이어 놓되, 서로 맞닿는 두 끝의 색이 항상 같아야 한다. 모든 막대를 정확히 한 번씩 사용해 이런 배열을 만들 수 있는지 판단하시오.
입력
입력은 EOF까지 주어지며, 각 줄에는 막대 하나의 양 끝 색을 나타내는 두 단어가 공백으로 구분되어 주어진다. 색 이름은 영어 소문자로만 이루어져 있고 길이는 10자 이하이다. 막대의 개수는 최대 250,000개이다.
출력
모든 막대를 조건에 맞게 일직선으로 놓을 수 있으면 Possible, 그렇지 않으면 Impossible을 출력한다.