임계 구조

Intelligence Cloud Privacy Company (ICPC)는 사용자에게 안전하고 강력한 클라우드 컴퓨팅 환경을 제공하는 것을 목표로 하는 세계적으로 유명한 클라우드 서비스 회사이다. ICPC의 엔지니어들은 1, 2, . . . , n으로 표시되는 n개의 컴퓨팅 노드와 m개의 통신 링크로 데이터 센터를 구축한다. 이 데이터 센터는 무방향 그래프 G = (V, E)로 모델링할 수 있으며, n개의 정점은 n개의 컴퓨팅 노드를 나타내고, 노드 i와 노드 j 사이에 통신 링크가 있으면 간선으로 연결된다. 이때 i와 j를 이 링크의 두 끝 노드라고도 한다. 또한 G의 임의의 두 노드 i와 j 사이에는 통신 링크가 최대 하나만 존재하고, 같은 노드 사이에는 통신 링크가 존재하지 않는다.

데이터 센터 G의 선형 배열 구조는 k ≥ 2인 노드의 수열 ⟨v0, v1, . . . , vk−1⟩로, 1 ≤ i ≤ k − 1인 임의의 연속한 두 노드 vi−1과 vi 사이에 통신 링크가 있고, 0 ≤ i ≤ k − 1인 vi가 모두 서로 다른 수열이다. 링 구조는 k ≥ 4인 노드의 수열 ⟨v0, v1, . . . , vk−1⟩로, 1 ≤ i ≤ k −1인 임의의 연속한 두 노드 vi−1과 vi 사이에 통신 링크가 있고, v0 = vk−1이며, 0 ≤ i ≤ k−2인 vi가 모두 서로 다른 수열이다. 데이터 센터 G는 임의의 두 노드 사이에 선형 배열이 존재하면 연결되어 있다고 하고, 그렇지 않으면 연결되어 있지 않다고 한다. ICPC의 한 연구팀은 프라이버시와 보안을 강화하기 위해 우아한 자원 할당 알고리즘을 사용하여 다음과 같은 임계 구조를 찾아야 한다:

1. 임계 노드: G에서 제거했을 때 G가 연결되어 있지 않게 되는 노드.
2. 임계 링크: G에서 제거했을 때 G가 연결되어 있지 않게 되는 통신 링크.
3. 임계 컴포넌트: G의 통신 링크 중, 집합의 임의의 두 통신 링크가 공통된 링 위에 있는 최대 집합.
4. 가장 큰 임계 컴포넌트: 통신 링크의 수가 최대인 임계 컴포넌트.

연결된 데이터 센터 G가 주어졌을 때, 임계 노드의 수, 임계 링크의 수, 그리고

μ* = (임계 컴포넌트의 수) / (가장 큰 임계 컴포넌트의 통신 링크 수) = p / q

를 계산하는 컴퓨터 프로그램을 작성해야 한다. 여기서 p/q는 μ*의 기약분수 형태이다.

입력 파일의 첫 번째 줄에는 다음과 같은 테스트 케이스의 수를 나타내는 정수 L (L ≤ 10)이 주어진다. 각 테스트 케이스의 첫 번째 줄에는 n과 m을 나타내는 두 정수가 공백으로 구분되어 주어진다. 그다음 바로 m개의 줄이 이어지며, 각 줄에는 통신 링크의 두 끝 노드를 나타내는 두 정수가 주어진다. 또한 연속한 두 정수는 공백으로 구분된다.

출력은 각 테스트 케이스마다 한 줄로 이루어진다. 각 줄에는 임계 노드의 수, 임계 링크의 수, p, q를 나타내는 네 개의 양의 정수가 주어진다. 여기서 p q는 μ*의 기약분수 형태이다. 연속한 두 정수는 공백으로 구분된다.

• 각 테스트 케이스에 대해 3 ≤ n ≤ 1000.
• n − 1 ≤ m ≤ n(n−1)/2
• 모든 L개의 테스트에서 m의 합은 106보다 작다.