AT_tkppc2016_g.貢物（Tribute）

joisino 姐姐的新工作是测试一款游戏。
在游戏中，主人公需要拜访不同的村庄以获取信息。
获取信息的方式是选择一些特定的贡品献给村庄（可以选择不献）。
有 $N$ 种贡品，编号从 $1$ 到 $N$。
同时，有 $M$ 个村庄，编号从 $1$ 到 $M$。
每个村庄都有自己的规定。
不同村庄的规定不会相同。
规定要求不能同时满足两个“条件”。每个“条件”可以是“献上某个贡品 $X$”或“不献上某个贡品 $X$”。
随着游戏的发展，村庄会进行合并。
在第 $i$ 次合并中，村庄 $P_i$ 和村庄 $Q_i$ 被合并为新的村庄 $M+i$。
合并时，确保村庄 $P_i$ 和村庄 $Q_i$ 存在，合并后，村庄 $P_i$ 和 $Q_i$ 消失。
新村庄会继承合并前村庄的所有规定。
合并过程一直进行，直到只剩下村庄 $2M-1$。
村庄 $1$ 到村庄 $M$ 都有遵守所有规定的贡品组合，但村庄 $M+1$ 到 $2M-1$ 可能会有相互矛盾的规定，导致无法同时满足所有规定。
joisino 姐姐的任务是编写一个程序，判断村庄 $M+1$ 到 $2M-1$ 是否有满足所有规定的贡品组合。

输入以以下格式给出：

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_M$ $B_M$ $P_1$ $Q_1$ $P_2$ $Q_2$ : $P_{M-1}$ $Q_{M-1}$

• 第 $1$ 行包含两个整数 $N(1 \le N \le 10^5)$ 和 $M(2 \le M \le 10^5)$，分别表示贡品种类数量和村庄数量。
• 接下来的 $M$ 行中，第 $i$ 行包含两个整数 $A_i(1 \le |A_i| \le N), B_i(1 \le |B_i| \le N)$，表示第 $i$ 个村庄的规定。
  • $A_i$ 和 $B_i$ 描述了两个“条件”：如果 $A_i$ 为正，则表示“献上贡品 $|A_i|$”；如果 $A_i$ 为负，则表示“不献上贡品 $|A_i|$”。$B_i$ 同理。
• 接下来的 $M-1$ 行中，第 $i$ 行包含两个整数 $P_i(1 \le P_i < M+i), Q_i(1 \le Q_i < M+i)$，表示合并的两个村庄。

输出应包括 $M-1$ 行。
对于第 $i$ 行，如果村庄 $M+i$ 存在符合所有规定的贡品组合，输出 "Possible"；否则输出 "Impossible"。

配点

这道题目设有部分分数。

3. 数据集 $1$ 满足 $M(1 \le M \le 10^3)$，正确解答可以得到 $15$ 分。
4. 数据集 $2$ 没有其他限制，正确解答可以得到 $125$ 分。

样例解释 1

例如，村庄 $5$ 可以选择什么都不献；村庄 $6$ 可以献上贡品 $1$ 和 $3$；村庄 $7$ 可以献上贡品 $2$。

本翻译由 AI 自动生成