1026 - 寻宝
时间限制 : 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