폭탄

시간 제한3초메모리 제한1024 MB

요약

방 0을 외부로 두는 다중 그래프에서, 문 하나와 폭탄 하나가 하루에 한 번만 통과할 수 있을 때 k개의 폭탄을 각 목표 방으로 옮기는 최소 일수를 구한다.

난이도: 어려움10점 중 8점
유형: 그래프, BFS, 최단 경로, 비트 연산
정답자: 아직 제출이 없습니다

문제

여러분의 팀은 무시무시한 BGO(Bureau of Global Overlords)가 세계 정복 계획을 세웠다는 사실을 알아냈다. 세계를 파멸에서 구할 유일한 방법은 BGO 본부를 폭파하는 것이다.

여러분에게는 $k$ 개의 폭탄이 있고, 전문가가 본부의 매우 정교한 평면도를 분석해 폭탄을 설치하기 가장 좋은 방들을 찾아냈다. 남은 문제는 하나뿐이다. BGO 본부의 문에는 다소 특이한 감시 시스템이 있어서, 폭탄은 문 감시가 하루에 허용하는 수상함의 기준값보다 아주 약간 낮은 수준이다. 따라서 하루에 주어진 문 하나를 통과할 수 있는 폭탄은 하나뿐이다. 게다가 감시 시스템은 폭탄을 몹시 불편하게 만드는 초고급 파동 기술을 사용하므로, 특정 폭탄 하나도 하루에 문 하나만 통과하는 것이 안전하다.

여러분의 잠행 능력이 무제한의 접근 권한을 준다고 가정할 때, 폭탄을 모두 설치하는 데 며칠이 필요한가?

입력

첫째 줄에 공백으로 구분된 세 정수 $n$ , $m$ , $k$ 가 주어진다. 첫 번째 정수 $1\leq n \leq 100$ 은 BGO 본부의 방 개수이며, 방에는 $1$ 부터 $n$ 까지의 번호가 붙어 있다. 편의상 폭탄이 처음에 모두 있는 바깥을 방 $0$ 으로 나타낸다.

두 번째 정수 $1 \leq m \leq 400$ 은 본부 내 방들 사이의 문 개수이다. 같은 두 방 사이에 여러 개의 문이 있을 수 있고, 일부 문은 바깥으로 통할 수도 있다. 세 번째 정수 $1 \leq k \leq 8$ 은 폭탄의 개수이다.

둘째 줄에는 공백으로 구분된 $k$ 개의 정수 $b_1, b_2, \ldots b_k$ 가 주어지며, 폭탄을 설치해야 하는 방들을 나타낸다(모든 $i$ 에 대해 $1 \leq b_i \leq n$ ).

마지막으로 $m$ 개의 줄이 주어지며, 각 줄은 문 하나를 나타낸다. 각 줄에는 서로 다른 두 정수 $0 \leq u, v \leq n$ 가 공백으로 구분되어 주어지며, 방 $u$ 와 방 $v$ 사이에 문이 있음을 뜻한다.

출력

폭탄을 모두 설치하는 데 필요한 최소 일수를 나타내는 정수 하나를 출력한다.

예제1

예제 1
입력
```
3 4 5
2 2 2 3 3
0 1
1 2
2 3
2 0
```
예상 출력
```
3
```