[WZOI2011 S3]食物中毒

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 medicine.in 输出文件 medicine.out

Problem 1  食物中毒 (medicine.pas/c/cpp)

 

 

背景

 

WZOI的小组成员今天集体食物中毒,什么事情也不能干了,这是一件十分可怕的事。幸 亏WZOIBqc同志十分在行化学,他可以马上制作出解药来……

 

问题描述

 

Bqc经过一段时间的研究发现,要解这种毒需要一种特殊的药物。不幸的是,这种药物在市面上不存在,没有办法Bqc只好亲自制得这种药物。它含有M种化学物质A1,A2,,AM。现 在Bqc的手上有N种药材(每种药材只有一种),每种药材含有若干种化学物质(Bqc他有一种 机器,只要将药材放入机器,就能制得相应的药物)。

Bqc需要你的帮助,他希望你能帮他选取若干种药材,用这些选取的药材制作出Bqc需要 的药物。由于这些化学物质是有毒的,因此你选出来的药物,必须含有这M种化学物质。

有一点需要注意:根据中医以毒攻毒的理论,两个相同的化学物质在一起,它们的药性会 同时消失变为一种无毒物质(大多情况下这种无毒物质会挥发掉,也就是说这种化学物质消 失了)。比如说药材1有化学物质1、2,药材2有化学物质1、3,那么如果药材1和药材2混合, 你得到的药物会含有化学物质2、3。

Bqc问你,需要选用那些药材可以制得他想要的药物?

 

输入格式

 

本题每个测试点存在多组数据,每组输入数据第1行包含两个整数NM,表示Bqc拥有的 药材数目和他所需药物所含的化学物质的种类数目;

第2行共有M个整数,分别表示M中化学物质的编号,用1~50之间的数字编号(输入数据保 证同一种化学物质不会被描述多次);

第3行到第N+2行,每行包含若干个数。第i+2行的第一个数为Mi,表示药材i包含Mi种化

学物质,接下来Mi个数,描述药材i含有的化学物质的编号,用1~50之间的数字编号(同一种

化学物质可能会被描述多次)。

每组输入数据用一个空行隔开。

 

输出格式

 

对于每组数据输出一行,如果用这些药材可以制得Bqc需要的药物,那么输出“Possible”; 否则输出“Impossible”,不包含引号。

 

样例输入输出

 

medicine.in

medicine.out

2 2

2 3

2 1 5

2 1 3

 

3 3

1 3 4

4 2 3 4 1

1 4

2 2 1


4 4

1 2 3 4

3 1 3 4

3 1 4 5

1 2

2 2 3



Impossible

Possible

Possible



样例解释

 

对于样例的第三组数据,可行的方案有选取 1、3 和选取 2、4.

 

数据规模

 

对于30%的数据,N10M20; 

对于50%的数据,N20M40; 对于100%的数据,N20M50

对于100%的数据,Mi50。 保证测试数据的组数不超过100。

 

时间限制

1s

 

提示

 

同一种化学物质被描述偶数次,那么说明这种物质不存在;否则这种物质存在。