Dima came to the horse land. There are n horses living in the land. Each horse in the horse land has several enemies (enmity is a symmetric relationship). The horse land isn’t very hostile, so the number of enemies of each horse is at most 3.
Right now the horse land is going through an election campaign. So the horses trusted Dima to split them into two parts. At that the horses want the following condition to hold: a horse shouldn’t have more than one enemy in its party.
Help Dima split the horses into parties. Note that one of the parties can turn out to be empty.
Input
The first line contains two integers n, m — the number of horses in the horse land and the number of enemy pairs.
Next m lines define the enemy pairs. The i-th line contains integers a i, b i (1 ≤ a i, b i ≤ n; a i ≠ b i), which mean that horse a i is the enemy of horse b i.
Consider the horses indexed in some way from 1 to n. It is guaranteed that each horse has at most three enemies. No pair of enemies occurs more than once in the input.
Output
Print a line, consisting of n characters: the i-th character of the line must equal “0”, if the horse number i needs to go to the first party, otherwise this character should equal “1”.
If there isn’t a way to divide the horses as required, print -1.
Examples
input
3 3
1 2
3 2
3 1
output
100
input
2 1
2 1
output
00
input
10 6
1 2
1 3
1 4
2 3
2 4
3 4
output
0110000000
Solution:
#include <cstdlib> #include <iostream> #include <iomanip> #include <stdio.h> #include <set> #include <vector> #include <map> #include <cmath> #include <algorithm> #include <memory.h> #include <string> #include <sstream> using namespace std; const int N = 333333; int n, m, i, ii, e, j; int kg[N], g[N][4], c[N], cnt[N]; set < pair <int, int> > s; int main() { srand(time(NULL)); scanf("%d %d", &n, &m); for (i=1;i<=n;i++) kg[i] = 0; for (i=1;i<=m;i++) { int ss, ff; scanf("%d %d", &ss, &ff); g[ss][kg[ss]++] = ff; g[ff][kg[ff]++] = ss; } while (1) { for (i=1;i<=n;i++) c[i] = cnt[i] = 0; s.clear(); for (i=1;i<=n;i++) s.insert(make_pair(-cnt[i], i)); while (!s.empty()) { int who = (*(s.begin())).second, cur[7]; s.erase(s.begin()); cur[0] = cur[1] = cur[2] = 0; for (j=0;j<kg[who];j++) cur[j]]]++; if (cur[1] < cur[2]) c[who] = 1; else if (cur[2] < cur[1]) c[who] = 2; else if (rand() & 1) c[who] = 1; else c[who] = 2; for (j=0;j<kg[who];j++) if (c[g[who][j]] == 0) { int z = g[who][j]; s.erase(make_pair(cnt[z], z)); cnt[z]++; s.insert(make_pair(cnt[z], z)); } } int bad = 0; for (i=1;i<=n;i++) { int qw = 0; for (j=0;j<kg[i];j++) if (c[g[i][j]] == c[i]) qw++; if (qw > 1) bad = 1; } if (!bad) break; } for (i=1;i<=n;i++) printf("%d", c[i]-1); printf("\n"); return 0; }