Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.2 kB
6
Indexable
#include<iostream>
using namespace std;

int T, d, n;
int arr[1005][1005], visit[1005];
int rs, flag;

void nhap() {
	cin >> d >> n;
	for(int i = 0; i < d; i ++) {
		for(int j = 0; j < d; j ++) {
			arr[i][j] = 0;
		}
	}
	for(int i = 0; i < n; i ++) {
		int a, b;
		cin >> a >> b;
		a --; b --;
		arr[a][b] = 1;
		arr[b][a] = 1;
	}
}

void reset() {
	for(int i = 0; i < d; i ++) {
		visit[i] = -1;
	}
}

void dequy(int gg, int t, int m = 1) {
	for(int i = 0; i < d; i ++) {
		if(arr[t][i] && visit[i] == -1) {
			visit[i] = m;
			for(int j = 0; j < d; j ++) {
				if(arr[i][j] && visit[j] == visit[i]) {
					flag = 1;
					return;
				}
			}
			int k = (m+1)%2;
			dequy(gg+1,i,k);
		}
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	cin >> T;
	for(int t = 1; t <= T; t ++) {
		rs = 0;
		nhap();
		reset();
		cout << "#" << t << " ";
		flag = 0;
		for(int i = 0; i < d; i++) {
			if(visit[i] == -1) {
				visit[i] = 0;
				dequy(0,0);
			}
			if(flag == 1) break;
		}
		if(flag == 0) for(int i = 0; i < d; i ++) cout << visit[i];
		else cout << -1;
		cout << endl;
	}
	return 0;
}