t

#include<iostream> using namespace std; int n,m, a[1000][1000]; int mau[1000]={-1}; int Answer; int visit[100]; int qu[1000000]; int f,r; int ck; bool checkdk(int x) { for(int i = 0; i< n; i++) if( a[x][i] == 1 && mau[i] == mau[x]) return false; return true; } void Try(int x) { if( x == n) { Answer ++; return; } for(int i = 0; i < 4; i++) { mau[x] = i; if(checkdk(x)) { Try(x+1); } mau[x] = -1; } } void Init() { f = r = 0; for(int i = 1; i <= n; i++){ visit[i] = 0; mau[i] = -1; } } int BFS(int x) { Init(); qu[r++] = x; mau[x] = 0; visit[x] = 1; int cur; while( f != r) { cur = qu[f++]; for(int i = 1; i <= n ; i++) { if( visit[i] == 0 && a[cur][i] == 1) { visit[i] = 1; mau[i] = 1 - mau[cur]; qu[r++] = i; }else if(visit[i] == 1 && a[cur][i]==1){ if( mau[i] == mau[cur] ) return -1; } } } return 1; } //void kt() //{ // for(int i = 1; i <= n; i++) // for(int j = 1; j <= n; j++) // if(a[i][j] == 1 && mau[i] == mau[j]) // ck = -1; // //} int main() { int test_case; int T; ios::sync_with_stdio(false); freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); cin >> T; for(test_case = 1; test_case <= T; ++test_case) { Answer = 0; cin >> n >> m; int x, y; for(int i = 1; i <=n ; i++) for(int j = 1; j <= n; j++) a[i][j] = 0; for(int i = 0; i < m ; i++) { cin >> x >> y; a[x][y] = 1; a[y][x] = 1; } ck = BFS(1); cout << "#" << test_case << " "; if(ck == -1) cout <<-1<<endl; else { for(int i = 1; i <= n; i++) cout << mau[i]; cout << endl; } } return 0; }