시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB169646.154%

문제

Your team has discovered that the fearsome Bureau of Global Overlords (BGO) have devised a plan for world domination; the only way to save the world from certain doom is to blow up the BGO headquarters.

You have $k$ bombs at your disposal, and an expert has analysed the headquarters super-intricate floor plan and pointed out the best rooms to place them. The last remaining problem is that the BGO headquarters has a somewhat peculiar surveillance system in their doors; the bombs are just a tiny tad below the threshold for the amount of suspiciousness the door surveillance accepts per day. Hence, each day only a single bomb may pass a given door in the headquarters. Moreover, the surveillance system is based on a type of ultrafancy wave technology that makes the bomb feel quite unwell -- it is only safe to carry a particular bomb through a single door each day as well.

Assuming your stealth skills grants you unlimited access, how many days are required to place the bombs?

입력

The first line contains three space-separated integers, $n$, $m$ and $k$. The first integer $1\leq n \leq 100$ denotes the number of rooms in the BGO headquarters; the rooms are labelled with numbers from $1$ to $n$ (inclusive). For simplicity we denote the outside (where all the bombs are initially) as room $0$.

The second integer $1 \leq m \leq 400$ denotes the number of doors between rooms in the headquarters. Note that there may be multiple doors between the same rooms, and that some doors may go to the outside. The third integer $1 \leq k \leq 8$ denotes the number of bombs.

On the second line follows $k$ space-separated integers $b_1, b_2, \ldots b_k$, indicating the rooms where the bombs should be placed ($1 \leq b_i \leq n$ for every $i$). 

Finally follows $m$ lines, each describing a door. Each such line contains two distinct space-separated integers $0 \leq u, v \leq n$ indicating that there is a door between room $u$ and room $v$.

출력

Output a single integer, the minimum number of days required to place the bombs.

예제 입력 1

3 4 5
2 2 2 3 3
0 1
1 2
2 3
2 0

예제 출력 1

3

출처

Contest > Bergen Open > Bergen Open 2021 B번

  • 문제를 만든 사람: Torstein Strømme