그래프의 세제곱

그래프 $G = (V, E)$의 세제곱 $G^3$은 정점 집합 $V$ 위에서 정의되는 그래프로, 두 정점 사이의 $G$에서의 거리가 3 이하일 때 두 정점을 간선으로 잇는다. 두 정점 사이의 거리는 두 정점을 잇는 최단 경로에 포함된 간선의 수이다.

다리(절단 간선)는 그 간선을 제거하면 연결 요소의 수가 늘어나는 간선이다. 동치로, 어떤 간선이 다리인 것은 그 간선이 어떤 사이클에도 포함되지 않는 것과 같다. 정점의 차수는 그 정점에 인접한 간선의 수이며, 두 끝점 중 어느 쪽도 차수가 1이 아닌 다리를 자명하지 않은 다리라고 한다.

이를 바탕으로 세 가지 개념을 정의한다.

• 어떤 정점에 인접한 모든 간선이 자명하지 않은 다리이면, 그 정점을 순수 다리 정점이라고 한다.
• 서로 다르고 서로 인접하며 각각 차수가 3 이상인 세 정점에 대해, 이 세 정점 중 정확히 하나에만 인접한 $G$의 모든 간선이 자명하지 않은 다리이면, 이 세 정점을 순수 다리 삼각형이라고 한다.
• 인접한 두 정점이 모두 순수 다리 정점이면, 이 두 정점을 순수 다리 쌍이라고 한다.

그림 1. 자명하지 않은 다리 7개를 점선으로 나타낸 연결 그래프. 순수 다리 정점은 7, 8, 15의 세 개, 순수 다리 삼각형은 $\{9, 10, 14\}$ 하나, 순수 다리 쌍은 $\{7, 8\}$ 하나가 있다.

임의의 연결 그래프의 세제곱은 해밀턴 연결이라는 사실이 알려져 있다. 즉 $G^3$의 임의의 두 정점은 해밀턴 경로로 이어진다.

연결 그래프가 주어질 때, 그 그래프의 순수 다리 정점, 순수 다리 삼각형, 순수 다리 쌍의 개수를 각각 구하여라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $m$이 주어지며, 각각 그래프 $G$의 정점 수와 간선 수이다. 여기서 $n \le 3000$, $m \le 1{,}000{,}000$이다. 이어지는 $m$개의 줄에는 각각 두 정수 $u$와 $v$가 주어지며, 이는 정점 $u$와 $v$를 잇는 간선을 뜻한다. 그래프는 연결되어 있으며 정점 집합은 $\{1, 2, \dots, n\}$이다.

각 테스트 케이스마다 한 줄에 세 정수를 하나의 공백으로 구분하여 출력한다. 순서대로 순수 다리 정점의 수, 순수 다리 삼각형의 수, 순수 다리 쌍의 수이다.