无向图的最短路径
时间限制:1000ms
内存限制:128MB
小明要处理一个题目,是求在无向图里面的最短路径。小明很苦恼,小亮表示小事一桩,轻松拿捏。小明不太相信,小亮表示随便考。
于是,小明找到一张图,里面有 n 个点 m 条边,小明会随机询问几个点,希望小亮能准确回答起点 1 到其他几个点的最短距离。
输入格式
第一行输入n,m 和 q,代表n个节点,m条边,q 个询问
后面m行,每行有x,y,代表x到y的一条路径
再后面 q 行是询问,每行一个整数,表示节点编号
输出格式
输出对应距离,如果无法到达输出 -1。
样例组
输入#1
6 5 2
1 3
3 5
4 5
4 2
1 4
5
6
输出#1
2
-1
提示说明
对于 10% 的数据,只有一个询问
对于 100% 的数据
1<=n,m<=1000,1<=u,v<=n,1<=q<=1000