투르 드 바이토티아

바이토티아에는 $n$개의 마을이 있다. 일부 마을 쌍은 양방향 도로로 연결되어 있으며, 도로는 끝점에서만 만나고 서로 교차하지 않는다 (터널과 고가도로 덕분에 평면 위에 교차 없이 놓을 수 있다).

곧 유명한 자전거 대회가 열린다. 대회 경로는 몇 개의 도로를 따라가며, 출발한 마을로 다시 돌아오고, 각 도로를 최대 한 번만 지난다. 즉, 같은 도로를 두 번 쓰지 않는 닫힌 경로다.

바이테아사르와 그의 동호회 친구들은 이 대회를 몹시 싫어해서, 자신들이 사는 마을을 대회 경로가 지나가지 못하게 하려 한다. 동호회 회원들이 사는 마을이 주어질 때, 그 마을들 중 어느 하나도 대회 경로가 지나갈 수 없도록 만들기 위해 막아야 하는 도로의 최소 개수를 구하여라.

첫째 줄에 세 정수 $n$, $m$, $k$ ($1 \le n \le 10^6$, $0 \le m \le 2 \cdot 10^6$, $1 \le k \le n$)가 공백으로 구분되어 주어진다. 각각 마을의 수, 도로의 수, 동호회 회원이 사는 마을의 수를 뜻한다. 마을에는 $1$번부터 $n$번까지 번호가 매겨져 있으며, 동호회 회원이 사는 마을은 정확히 $1$번부터 $k$번까지이다.

이어지는 $m$개의 줄에는 각각 두 정수 $a_i$, $b_i$ ($1 \le a_i < b_i \le n$)가 공백으로 구분되어 주어지며, 마을 $a_i$와 $b_i$가 양방향 도로로 연결되어 있음을 뜻한다. 임의의 두 마을은 최대 하나의 도로로 직접 연결된다.

대회 경로가 동호회 회원이 사는 어떤 마을도 지나갈 수 없도록 만들기 위해 막아야 하는 도로의 최소 개수를 한 줄에 정수 하나로 출력하여라.