술집과 집 배치

3년 조금 넘게 전, 당신은 몰바니아의 대통령으로 당선됐다. 몰바니아는 경치가 좋지만 현대 치과 의술이 닿은 적 없는 나라다. 선거에서 크게 이기려고 공약을 몇 가지 내걸었는데, 지금 돌아보면 그중 몇 개는 좀 과했다.

몰바니아의 경제는 다른 나라보다 단순하다. 주요 직업은 술집 주인과 맥주 애호가 둘뿐이고, 이 두 집단이 국내총생산의 75퍼센트가 넘는 몫을 차지한다. 맥주 애호가는 맥주값을 치르려고 돈을 빌리고, 그 돈은 술집 주인의 수입이 된다. 술집 주인은 그 수입으로 맥주 애호가에게 나간 대출을 담보로 삼은 AAA 등급 채권을 산다. 몰바니아 사람은 이 구조를 펍프라임 대출이라고 부른다.

공약 가운데 하나가 도시 계획 개선이었다. 당신은 건설 부지를 여러 곳 골라 두었고, 각 부지에는 술집이나 맥주 애호가의 집 중 하나를 짓는다. 일부 부지 쌍은 보도로 이어져 있다. 모든 집은 보도 하나 거리에 술집이 적어도 하나 있어야 하고, 모든 술집은 보도 하나 거리에 집이 적어도 하나 있어야 한다. 그런 배치가 아예 없는 도시도 있고, 그때는 그렇다고 답해야 한다.

이 도시의 구조는 독특하다. 보도를 평면 지도 위에 서로 교차하지 않게 그릴 수 있다고 가정하면 안 된다.

첫째 줄에 건설 부지의 수 $n$과 보도의 수 $m$이 주어진다 ($1 \le n \le 10000$, $0 \le m \le 100000$). 부지 번호는 1번부터 $n$번까지다.

다음 $m$개 줄에는 각각 정수 $x$와 $y$가 주어진다 ($1 \le x, y \le n$, $x \ne y$). 부지 $x$와 부지 $y$를 잇는 보도가 있다는 뜻이다. 같은 줄이 두 번 주어지는 경우는 없다.

모든 술집 옆에 집이 있고 모든 집 옆에 술집이 있는 배치가 없으면 Impossible을 출력한다.

그렇지 않으면 단어 $n$개를 공백 하나로 구분해 출력한다. $i$번째 단어는 부지 $i$에 짓는 건물에 따라 pub 또는 house다.

조건을 만족하는 배치가 여러 개일 수 있으므로, 다음 규칙이 만드는 배치를 출력한다. 부지 위에서 깊이 우선 탐색을 실행한다. 부지를 번호가 작은 쪽부터 훑으면서 아직 방문하지 않은 부지마다 탐색을 새로 시작하고, 탐색을 시작한 부지의 깊이는 0이다. 탐색이 어떤 부지에 도착하면 그 부지와 보도로 이어진 부지를 번호가 작은 쪽부터 확인해 아직 방문하지 않은 첫 부지로 들어간다. 이렇게 들어간 부지의 깊이는 직전 부지의 깊이보다 1 크다. 깊이가 짝수인 부지에는 pub을, 홀수인 부지에는 house를 출력한다.