#include <iostream>
using namespace std;
int temp;
int x, y;
int T,n,m;
int a[1005][1005];
int dinh[1005];
bool visit[1005] = {false};
int front,rear;
int que[1005];
int main()
{
freopen("input.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++)
{
temp = 0;
cin >> n;
cin >> m;
for (int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
a[i][j] = 3;
visit[i] = false;
}
for (int i = 1; i <= m; i++)
{
cin >> x;
cin >> y;
a[x][y] = 1;
a[y][x] = 1;
}
int k;
front = 0; rear = 0;
que[rear++] = 1;
dinh[1] = 0;
visit[1] = true;
while (front < rear)
{
k = que[front++];
for(int j = 1; j <= n; j++)
{
if(a[k][j] == 1 && visit[j] == false)
{
if(dinh[k] == 0)
{
dinh[j] = 1;
que[rear++] = j;
}
if(dinh[k] == 1)
{
dinh[j] = 0;
que[rear++] = j;
}
visit[j] = true;
}
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <=n; j++)
{
if(a[i][j] == 1 && dinh[i] == dinh[j])
temp = -1;
}
}
cout << "#" << tc << " ";
if( temp == -1 ) cout << "-1" << endl;
else
{
for(int i = 1; i <= n; i++)
cout << dinh[i];
cout << endl;
}
}
}
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.