← 返回 openai 的题目列表Minimum Time to Infect a Network
类型：online_judge
Problem: Minimum Time to Infect a Network
You are given an undirected graph representing a network. Nodes are labeled from 0 to n - 1. Initially, some nodes are infected.
Every minute, all infected nodes simultaneously infect all of their uninfected neighbors. Return the minimum number of minutes needed to infect every node. If some nodes can never be infected, return -1.
Input
The first line contains two integers n and m, the number of nodes and edges.
The next m lines each contain two integers u v, representing an undirected edge.
The next line contains an integer k, the number of initially infected nodes.
The last line contains k integers, the initially infected node labels.
Output
Print one integer: the number of minutes needed to infect all nodes, or -1 if impossible.
Constraints
1 <= n <= 100000
0 <= m <= 200000
1 <= k <= n
The graph may be disconnected.
Example
Input:
6 5
0 1
1 2
2 3
3 4
2 5
1
0
Output:
4
Example
Input
6 5
0 1
1 2
2 3
3 4
2 5
1
0
Output
4