23324번 - 어려운 모든 정점 쌍 최단 거리

문제

연두는 방금 "플로이드 와샬 알고리즘"을 공부했다. 이 알고리즘은 $N$개의 정점으로 이루어진 그래프에서, 모든 정점 쌍의 최단 거리를 $O(N^3)$에 구해준다.

신이 난 연두는 자신이 좋아하는 그래프를 하나 가져왔다. 이 그래프는 $N$개의 정점과 $M$개의 양방향 간선으로 이루어진 단순 연결 그래프이며, 정점에는 1,ドル 2, \dots, n$으로 번호가 매겨져있다. 또한 딱 하나의 간선에만 1ドル$의 가중치가 있고 나머지 간선은 가중치가 0ドル$이다.

이제 이 그래프에서 모든 정점 쌍의 최단 거리의 합을 구해보려고 한다. 즉, 1ドル \le i < j \le N$를 만족하는 모든 $\frac{N(N-1)}{2}$개의 쌍 $(i,j)$에 대해, $i$번 정점과 $j$번 정점간의 최단거리를 전부 더한 값을 구할 것이다.

연두는 신나서 코드를 짰지만 한참 동안 기다려도 결과가 나오지 않았다. 절망에 빠진 연두는 더 좋은 방법을 생각해 냈는데, 바로 대회에 이 문제를 출제하여 여러분들이 답을 대신 구하게 하는 것이다.

입력

첫 번째 줄에 정점의 개수 $N$(2ドル \le N \le 100,000円$), 간선의 개수 $M$(1ドル \le M \le 200,000円$), 정수 $K$(1ドル \le K \le M$)가 주어진다.

다음 $M$개의 줄에 걸쳐 $u_i$와 $v_i$가 주어진다. 이것은 $i$번째 간선은 $u_i$와 $v_i$를 잇는다는 것을 의미한다. (1ドル \le u_i, v_i \le n, u_i \ne v_i$)

단순 연결 그래프만 입력으로 주어지며, $K$번째 간선의 가중치는 1ドル$이고, 나머지 간선의 가중치는 0ドル$이다.

출력

모든 정점 쌍의 최단 거리의 합을 출력한다.

출력의 값이 32비트형 정수(C/C++의 int)의 최댓값을 넘을 수 있음에 주의하자.

제한

힌트