Building a Tree

Given an undirected graph and a root vertex R, choose a spanning tree of the graph and root it at R. Then every vertex except R has exactly one parent.

Define SFD as the sum, over all non-root vertices v, of the degree of parent(v). The degree of a vertex is measured in the original graph, not in the chosen spanning tree; it is the number of vertices adjacent to that vertex in the original graph.

Compute the minimum possible SFD over all spanning trees rooted at R.

The first line contains three integers N, M, and R (2 <= N <= 1,000, N-1 <= M <= N*(N-1)/2, 1 <= R <= N). N is the number of vertices, M is the number of edges, and R is the root vertex.

Each of the next M lines contains two integers A and B (1 <= A, B <= N), describing an edge between two distinct vertices A and B. No edge appears more than once.

Print the minimum possible SFD on the first line.