대흥민 카페 다녀왔습니다

어제 손흥민 카페 다녀왔습니다. 손흥민 카페가 열린 건 아니고요, 그냥 카페에서 대흥민 생각했습니다

카페에 간 건 아니고요, 그냥 집에서 커피를 마셨습니다. 사실 커피도 안 마셨습니다

그냥 대흥민인 상태입니다

손흥민의 열렬한 팬인 종학이는 종종 자신이 손흥민이라고 상상하곤 한다. 대한민국의 캡틴 손흥민은, 언제나 그렇듯 자신을 향해 달려오는 수비수들을 피해 최대한 오래 드리블을 해야 한다.

어이없겠지만 축구장을 $N$개의 정점과 서로 다른 두 정점을 잇는 $M$개의 양방향 간선으로 구성된 그래프라고 생각해 보자. 이 중 $K$개의 정점에는 손흥민을 저지하고자 하는 수비수가 있다. 정점은 $1$번부터 시작하며 축구장에서 갈 수 없는 정점이 있어서는 안 되므로, 임의의 두 정점 사이에는 뛰어갈 수 있는 경로가 항상 존재한다.

경기가 시작할 때 손흥민은 $1$번 정점에, 수비수들은 $1$번 정점을 제외한 $K$개의 정점에 위치한다. 손흥민은 수비수들을 피해 최대한 긴 시간 동안 드리블을 하고자 한다.

매초가 시작되면, 손흥민과 $K$명의 수비수들은 순서에 따라 다음과 같이 행동한다:

1. 손흥민은 현재 정점에 머무르거나, 수비수가 없는 인접한 정점으로 뛰어간다.
2. 각 수비수는 손흥민이 위치한 정점으로의 최단 경로에 포함된 인접한 정점으로 뛰어간다. 여기서 최단 경로란, 두 정점을 잇는 경로 중 가장 적은 수의 간선을 이용하는 경로를 의미한다. 만약 가능한 정점이 여러 개인 경우 번호가 가장 작은 정점으로 뛰어간다.

한 정점에 여러 명의 수비수가 동시에 있을 수 있음에 유의하자. 또한 손흥민이 현재 정점에 머무르고 있는 상황 역시 드리블로 간주한다.

만약 손흥민과 어떤 수비수가 같은 정점에 위치하게 된다면, 손흥민은 아쉽게도 그 수비수에게 저지당하게 된다. 손흥민이 수비수들을 피해 드리블할 수 있는 최대 시간을 출력해 보자. 만약 손흥민이 수비수들을 피해 영원히 드리블할 수 있다면 DaeHeungMin을 출력한다.

첫 번째 줄에 정점의 개수 $N$, 간선의 개수 $M$, 수비수의 명수 $K$가 공백으로 구분되어 주어진다. $(2\leq N \leq 16;$ $N-1 \leq M \leq N(N-1)/2;$ $1 \leq K \leq N - 1)$ 

두 번째 줄부터 $M$개의 줄에 걸쳐 두 개의 정수 $a\_i$와 $b\_i$가 공백으로 구분되어 주어진다. 이는 정점 $a\_i$와 $b\_i$를 연결하는 간선이 존재한다는 의미이다. 어떤 두 정점을 잇는 간선은 최대 한 번만 주어진다. $(1\leq i \leq M;$ $1\leq a\_i, b\_i \leq N;$ $a\_i \neq b\_i)$ 

마지막 줄에는 $K$개의 정수 $p\_j$가 공백으로 구분되어 주어지며, 이는 초기에 $j$번째 수비수가 정점 $p\_j$에 위치해 있다는 의미이다. 입력으로 주어지는 수비수의 초기 위치는 서로 다르다. $(1 \leq j \leq K;$ $2\leq p\_j \leq N)$

손흥민이 수비수에게 저지당하지 않고 드리블할 수 있는 최대 시간을 출력한다. 만약 영원히 드리블 할 수 있다면 DaeHeungMin을 출력한다.