langmac

Level 3
Làng mạc
Cho bản đồ mạng lưới giao thông giữa các làng mạc. Một vùng được định nghĩa là một tập hợp các làng mà từ bất kỳ một làng nào trong vùng đều có thể đi đến một làng khác trong vùng.

Hãy tính số vùng trong bản đồ, số làng cô lập (làng không có đường đi đến bất kỳ làng khác) và số con đường đóng vai trò là “Cầu” giữa hai vùng (nếu bỏ con đường này đi thì số lượng vùng tăng lên 1).

Input

Dòng đầu có một số T là số lượng test của file input. Mỗi test được bố cục như sau: dòng đầu là một số nguyên dương N (N <= 300) N là số làng, tiếp theo là một ma trân A[i, j] trong đó A[i][j] có giá trị bằng 1 là có đường đi từ làng i tới làng j và 0 nếu không có đường từ làng i tới làng j. Dữ liệu đảm bảo nếu có đường từ làng i tới làng j thì cũng sẽ có đường ngược lại.

Output

Với mỗi test, in ra sốvùng có trên bản đồ, số làng cô lập và số đường đóng vai trò là cầu.

 

Sample

 

Input

2
5
0 1 0 1 0
1 0 0 1 0
0 0 0 0 1
1 1 0 0 0
0 0 1 0 0
7
0 0 0 1 0 0 1
0 0 0 1 0 0 0
0 0 0 0 1 0 0
1 1 0 0 0 0 1
0 0 1 0 0 0 0
0 0 0 0 0 0 0
1 0 0 1 0 0 0

 

Output

2 0 1
3 1 2


2 0 1
3 1 2
3 0 4
1 0 0
10 10 0
1 0 0
2 0 5
1 0 0
3 2 4
6 5 7
24 23 1
1 0 3
10 9 12
3 2 5
7 5 6
12 5 13
1 0 11
3 2 3
1 0 4
7 6 5
25 25 0
9 5 16
9 8 5
25 25 0
1 0 5
2 1 4
3 2 6
1 0 0
1 0 0
1 0 0
1 0 0
1 0 1
1 0 0
1 0 0
1 0 0
1 0 1
1 0 1
22 16 28
4 2 7
1 0 0
41 36 9
1 0 0
1 0 0
1 0 0
2 1 3
1 0 0
40 31 10
2 1 1
1 0 0
300 300 0


#include <iostream>
using namespace std;

int T, n, arr[301][301];

int cnt[301];
bool vs[301];

int r1, r2, r3;

void resetVs(){
	for(int i = 0; i < n; i++) vs[i] = false;
}

void dfs(int index){
	if(vs[index]) return;
	vs[index] = true;
	for(int i = 0; i < n; i++){
		if(arr[index][i]) dfs(i);
	}
}

void solveProblem(){
	for(int i = 0; i < n; i++){
		if(!vs[i]){
			r1++;
			dfs(i);
		}
	}
	for(int i = 0; i < n; i++){
		if(!cnt[i]) r2++;
		for(int j = i + 1; j < n; j++){
			if(arr[i][j]){
				resetVs();
				arr[i][j] = 0, arr[j][i] = 0;
				dfs(i);
				arr[i][j] = 1, arr[j][i] = 1;
				if(!vs[j]) r3++;
			}
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;
	
	for(int tc = 1; tc <= T; tc++){
		// Input
		int c0 = 0, c1 = 0;
		cin >> n;
		for(int i = 0; i < n; i++){
			cnt[i] = 0;
			for(int j = 0; j < n; j++){
				cin >> arr[i][j];
				if(i == j) arr[i][j] = 0;
				cnt[i] += arr[i][j];	
				if(arr[i][j]) c1++;
				else c0++;
			}
		}

		// Initial
		r1 = 0, r2 = 0, r3 = 0;
		resetVs();

		// Solve Problem
		if(c0 == n*n) r1 = n, r2 = n, r3 = 0;
		else if(c1 == n*n - n) r1 = 1, r2 = 0, r3 = 0;
		else solveProblem();

		// Output
		cout << r1 << " " << r2 << " " << r3 << endl;
	}

	return 0;
 }