시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 7 0 0 0.000%

문제

주어진 그래프의 한 노드를 루트로 갖는 스패닝 트리는 여러 개이다. 한 (루트가 있는) 스패닝 트리에서, 루트가 아닌 모든 정점들에 대해서, 그 정점의 부모 정점의 차수의 총 합을 SFD(Sum of Father's Degree)라 한다. 이 때 각 정점들의 차수는 스패닝 트리에서가 아니라 원래 그래프에서의 차수를 의미한다. 그래프에서 어떤 정점의 차수는 그 정점에 연결된 정점들의 개수를 의미한다.

이해를 돕기 위해 위의 그림을 보자. 제일 왼쪽 그림은 하나의 그래프이고, 오른쪽의 두 개의 그림은 그 그래프의 루트가 있는(1번 정점) 스패닝 트리를 두 개 나타낸 것이다. 가운데 그림의 경우에는 루트를 제외한 2, 3, 4, 5번 정점에 대해서, 그 부모 정점이 1번 정점이 된다. 1번 정점의 원래 그래프에서의 차수가 4이므로, 이 경우 SFD는 4+4+4+4=16가 된다. 세 번째 그림에서는 부모 정점들이 각각 1, 2, 3, 4 이므로 이 경우 SFD는 4+3+3+3=13이 된다. 그리고 이러한 경우가 최적인 경우이다.

그래프와 루트가 주어졌을 때, SFD의 최소값을 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 N(1≤N≤1,000), M(1≤M≤N×(N-1)/2), R(1≤R≤N)이 주어진다. N은 정점의 개수, M은 간선의 개수, R은 루트의 번호이다. 다음 M개의 줄에는 각 간선에 대한 정보를 나타내는 두 정수 A, B(1≤A, B≤N)가 주어진다. 이는 그 간선이 연결하고 있는 서로 다른 두 정점의 번호이다. 같은 간선이 여러 번 주어지는 경우는 없다.

출력

첫째 줄에 SFD의 최소값을 출력한다.

예제 입력

5 8 3
5 2
5 3
3 2
5 1
1 3
3 4
4 2
1 4

예제 출력

13

힌트