三年前，你当选了光荣而风景如画的莫尔瓦尼亚（Molvanîa）国家的总统，这是一个未受现代牙科技术影响的国度。为了在选举中取得压倒性胜利，你不得不做出一些承诺，事后看来，其中一些承诺可能稍微有些夸大。

莫尔瓦尼亚的经济与大多数其他国家相比非常简单。莫尔瓦尼亚的两个主要职业是酒吧老板和啤酒饮用者。这两个群体加起来占莫尔瓦尼亚 GDP（国内生产总值）的 75% 以上。简单来说，该系统运作如下：啤酒饮用者借钱支付他们的啤酒费用。这为酒吧老板创造了收入。酒吧老板利用他们的收入购买由啤酒饮用者贷款支持的 AAA 级债券。这个系统在当地被称为“酒吧次级贷款”（pub-prime lending）。

Photo by National Library of Australia

任务

你在竞选时的承诺之一是通过改善城市规划来进一步优化莫尔瓦尼亚的“虎式经济”。你已经确定了若干个合适的建筑工地，每个工地都可以建造一个酒吧或一个啤酒饮用者的房子。这些工地之间存在一些人行道。为了充分优化经济，你希望放置建筑物，使得每栋房子在一个人行道距离内至少有一个酒吧，且每个酒吧在一个人行道距离内至少有一栋房子。这可能无法实现，但你会尽力而为。

请注意，这座城市的布局非常奇特，甚至可能无法在普通地图上绘制出来。莫尔瓦尼亚就是这么特别。

输入格式

城市中有 $n$ 个建筑工地和 $m$ 条人行道（$1 \le n \le 10\,000$ 且 $0 \le m \le 100\,000$）。第一行包含 $n$ 和 $m$，由单个空格分隔。接下来的 $m$ 行包含整数 $x$ 和 $y$（$1 \le x, y \le n$），表示 $x$ 和 $y$ 之间有一条人行道。不存在自环（即 $x \neq y$），且所有描述人行道的行都是不同的。

输出格式

如果无法建造酒吧和房子，使得每个酒吧都邻近一栋房子且每栋房子都邻近一个酒吧，则输出一行 Impossible。否则，输出 $n$ 个由空格分隔的单词。对于每个建筑工地，输出 pub 或 house。第一个单词表示在建筑工地 1 建造什么，第二个表示工地 2，依此类推。如果有多个有效的解决方案，你可以输出其中任何一个。

样例

输入格式 1

4 4
1 2
2 3
3 4
4 1

输出格式 1

pub house pub house

输入格式 2

4 4
1 2
2 3
3 4
4 2

输出格式 2

pub house pub house