問題文
joisino姐姐的下一个工作是游戏的测试。
在这个游戏中,主人公为了获取信息,会访问各种村庄。
从村民处获取信息,需要适当地选择一些贡品,并献给村子(这里,0个贡品可献,也就是说可以不献任何东西)。
贡品的种类编号为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 ≦ N ≦ 10^5),以及一个整数,表示村庄的数量M(2 ≦ M ≦ 10^5)。 表示
- 继续M行i行中,i表示第几村庄的规定的整数。A_i(1≦|A_i|≦N),B_i(1≦|B_i|≦N)(|A_i|≠|B_i|)。 表示
- 在这里,A_i,B_i分别表示“条件”,A_i,B_i两个条件不能同时满足是村庄i的规定。
- A_i为正数时表示贡品|A_i|表示奉献的条件,A_i为负时,表示不奉献|A_i|。B_i也是如此。
- 继续M-1行i行显示要合并的村庄的整数,P_i(1≦P_i<M+i),Q_i(1≦Q_i<M+i)。 表示
配点
针对此问题设置了部分分数。
出力
输出是
由M-1行组成。
i行显示关于村庄M+i,如果存在遵守所有规矩的奉献组合,"Possible",如果没有"Impossible"。
在第
入力例1
3 4 1 2 -2 -3 -1 3 1 -2 1 3 2 5 6 4
出力例1
Possible Possible Possible
例如,村庄5可以不奉献任何东西,村庄6可以奉献{1和3},村庄7可以奉献{2可以奉献}。
入力例2
3 4 -1 -2 2 3 1 -2 2 -3 1 4 2 5 6 3
出力例2
Possible Possible Impossible
入力例3
4 20 3 -2 4 -3 3 -1 -2 -3 -1 2 2 -4 2 -3 4 -1 1 4 -1 -3 4 2 1 -3 -2 -1 2 3 3 -4 -4 -2 -4 1 -1 -4 2 1 -4 -3 1 11 16 2 6 20 8 12 22 15 18 5 23 7 9 10 13 26 19 21 4 3 28 31 14 24 27 30 29 25 17 34 36 32 35 33 37 38
出力例3
Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Possible Impossible Possible Impossible