사이클 없는 그래프 만들기

$N$개의 정점과 $M$개의 간선을 가진 무향 그래프 $G$가 주어진다. 시간 $T=1$일 때, $G$에서 정해진 $K$개의 정점을 지운다. $T=t\ (1 < t)$일 때는 $T=t-1$에서 지워진 정점과 이웃하였던 정점들을 지운다. 이때 $G$에 사이클이 존재하지 않는 최초의 시간 $T=C$를 구하는 프로그램을 작성하여라.

처음 주어지는 그래프 $G$는 모든 정점이 연결된 연결 그래프이며, 사이클이 존재한다. 또한 정점이 삭제되면 해당 정점과 연결된 간선도 함께 없어진다. 자기 자신과 연결된 간선은 주어지지 않으며, 중복된 간선이 주어질 수 있다.

첫 번째 줄에 그래프 $G$의 정점의 수 $N$과 간선의 수 $M$, 시간 $T=1$일 때 삭제하는 정점의 수 $K$가 공백으로 구분되어 주어진다. $(2\le N\le M\le 200\\, 000;$ $1\le K\le N)$

두 번째 줄부터 $M$개의 줄에 걸쳐 간선의 정보 $u, v$가 공백으로 구분되어 주어진다. 이는 $u$번 정점과 $v$번 정점이 간선으로 연결되어 있음을 의미한다. $(1\le u,v\le N;$ $u \ne v)$

그 다음 줄에는 $T=1$일 때 삭제하는 정점의 번호 $K$개가 공백으로 구분되어 주어진다.

첫 번째 줄에 $T=C$에서 정점을 지우고 처음으로 사이클이 존재하지 않게 되었을 때의 시간 $C$를 출력한다.

$G$의 사이클은 $G$의 부분그래프 중 비어있지 않고 연결되어 있으며, 모든 정점의 차수가 $2$인 그래프를 의미한다.