1026 - 寻宝

通过次数

9

提交次数

60

时间限制 : 1 秒
内存限制 : 128 MB

寻宝游戏中有红宝石和蓝宝石,每个点至多存在一种宝石。 在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