P6517 [CEOI 2010] alliances (day1)

在一个幻想世界里，有块矩形岛屿。这座岛屿被划分成了 $R$ 行 $C$ 列的方格。 有些方格无人居住，而有些方格被以下某一种生物占据：精灵，人类，矮人或者霍比特人。占据同一格子的生物在这一格子组成了一个村庄。 为了防止恶魔的袭击，他们需要结成联盟。定义**每个村庄相邻四个方向（上下左右）的村庄**为这个村庄的邻居。 每种生物分别要满足以下条件： - 精灵：只需要与一个邻居结盟； - 人类：需要与两个邻居结盟，且这两个邻居不能在上下或者左右方向； - 矮人：需要与三个邻居结盟； - 霍比特：需要与四个邻居结盟（即所有邻居）。 你的任务是确定岛上的所有村庄是否都能与相应数量的邻居结盟（即可能会出现一些邻居并没有结盟）。如果能，则输出联盟的结构。否则输出 `Impossible!`。 **注意：结盟的关系是双向的。**

无

无

#### 数据规模与约定 - 对于 $55\%$ 的数据，保证 $\min(r,c)\le 10$； - 对于另 $15\%$ 的数据，保证 $r\times c\le 20$； - 对于另 $10\%$ 的数据，保证地图中只有无人区和人类； - 对于 $100\%$ 的数据，保证 $1\le r,c\le 70$。 #### 说明 **题目译自 [CEOI 2010](http://ceoi2010.ics.upjs.sk/Contest/Tasks) day 1 *[T1 alliances](https://people.ksp.sk/~misof/ceoi2010/all-eng.pdf)***。 翻译版权为题目提供者 @[ShineEternal](https://www.luogu.com.cn/user/45475) 所有，未经许可禁止转载。