시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB (추가 메모리 없음)191948352.866%

문제

연두는 방금 "플로이드 와샬 알고리즘"을 공부했다. 이 알고리즘은 $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)의 최댓값을 넘을 수 있음에 주의하자.

예제 입력 1

5 4 2
1 2
2 3
3 4
4 5

예제 출력 1

6

각 정점 쌍에 대한 최단거리는 다음과 같다

  • $1 \leftrightarrow 2$ : $0$
  • $1 \leftrightarrow 3$ : $1$
  • $1 \leftrightarrow 4$ : $1$
  • $1 \leftrightarrow 5$ : $1$
  • $2 \leftrightarrow 3$ : $1$
  • $2 \leftrightarrow 4$ : $1$
  • $2 \leftrightarrow 5$ : $1$
  • $3 \leftrightarrow 4$ : $0$
  • $3 \leftrightarrow 5$ : $0$
  • $4 \leftrightarrow 5$ : $0$

예제 입력 2

3 3 1
1 2
2 3
3 1

예제 출력 2

0

힌트

단순 연결 그래프란 다음 조건들을 모두 만족하는 그래프를 의미한다.

  • 어떤 정점 $u$와 다른 정점 $v$를 잇는 간선 $u-v$는 최대 한 개이다.
  • 어떤 정점 $u$를 스스로 연결하는 간선 $u-u$는 존재하지 않는다.
  • 어떤 정점 $u$에서 다른 정점 $v$까지 한 개 이상의 간선을 이용하여 항상 도달할 수 있다.

출처

University > 홍익대학교 > 2021 홍익대학교 프로그래밍 경진대회 E번