1707: [NewOJ Contest 1] 寻宝

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:73 通过:9

题目描述

寻宝游戏中有红宝石和蓝宝石,每个点至多存在一种宝石。
在n个点的单向图中,玩家每占领一个点,都需要在这个点上插上一面旗帜。
最开始玩家占领起点1,已经在起点1插入一面旗帜,之后每次只能从已经占领的点出发,然后占领相邻的点,当占领区域中至少包含1个红宝石和1个蓝宝石时,游戏胜利。
请问玩家最少还需要多少面旗帜可以胜利(不包括起点1的旗帜)。

输入格式

输入第一行包含三个正整数n,m,k(2≤n≤10^5,1≤m,k<n),分别表示点数、红宝石总数、蓝宝石总数。
第二行包含m个数字,表示包含红宝石的点。
第三行包含k个数字,表示包含蓝宝石的点。
接下来n行,第i行:第一个数字k表示点i的出度,第2到k+1个数字表示点i可到达的点。

输出格式

如果不可能胜利,输出“impossible”,否则输出一个数字表示答案。

输入样例 复制

样例1:
3 1 1
2
3
1 2
2 3 1
1 1

样例2:
3 1 1
2
3
1 2
1 1
2 1 2

输出样例 复制

样例1:
2

样例2:
impossible