트리 만들기

무방향 그래프와 루트 정점 R이 주어진다. 이 그래프의 스패닝 트리 하나를 고르고 R을 루트로 정하면, R을 제외한 모든 정점은 부모 정점을 하나씩 가진다.

SFD는 루트가 아닌 모든 정점 v에 대해 parent(v)의 차수를 더한 값이다. 여기서 차수는 선택한 스패닝 트리에서의 차수가 아니라, 원래 그래프에서 그 정점과 인접한 정점의 개수를 뜻한다.

R을 루트로 하는 모든 스패닝 트리 중 SFD의 최솟값을 구하시오.

첫째 줄에 세 정수 N, M, R(2 <= N <= 1,000, N-1 <= M <= N*(N-1)/2, 1 <= R <= N)이 주어진다. N은 정점의 개수, M은 간선의 개수, R은 루트 정점의 번호이다.

다음 M개의 줄에는 간선 하나를 나타내는 두 정수 A, B(1 <= A, B <= N)가 주어진다. 이는 서로 다른 두 정점 A와 B를 잇는 간선을 의미한다. 같은 간선이 여러 번 주어지지 않는다.

첫째 줄에 가능한 SFD의 최솟값을 출력한다.