2255번 - 트리 만들기

주어진 그래프의 한 노드를 루트로 갖는 스패닝 트리는 여러 개이다. 한 (루트가 있는) 스패닝 트리에서, 루트가 아닌 모든 정점들에 대해서, 그 정점의 부모 정점의 차수의 총 합을 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(2 ≤ N ≤ 1,000), M(N-1 ≤ M ≤ N×(N-1)/2), R(1 ≤ R ≤ N)이 주어진다. N은 정점의 개수, M은 간선의 개수, R은 루트의 번호이다. 다음 M개의 줄에는 각 간선에 대한 정보를 나타내는 두 정수 A, B(1 ≤ A, B ≤ N)가 주어진다. 이는 그 간선이 연결하고 있는 서로 다른 두 정점의 번호이다. 같은 간선이 여러 번 주어지는 경우는 없다.

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