New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

1707: [NewOJ Contest 1] 寻宝

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：237 通过：43
提交提交记录统计

题目描述

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