UVa 11396 - Claw Decomposition

// UVa 11396 - Claw Decomposition

#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;

vector<int> adj[301];
int color[301], oo;

bool coloring(int a, int c) {
	//printf("%d %d\n", a, c);
	color[a] = c;
	for (int j = 0; j < adj[a].size(); j++) {
		int b = adj[a][j];
		if (color[b] == oo) {
			if (!coloring(b, c ^ 1))
				return false;
		} else if (color[b] == color[a])
			return false;
	}
	return true;
}

int main() {
	int n;
	while (scanf("%d", &n) && n) {
		int a, b;
		for (int i = 1; i <= n; i++)
			adj[i].clear();
		while (scanf("%d %d", &a, &b) && a && b) {
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		memset(color, 127, sizeof(color));
		oo = color[0];
		if (coloring(1, 0))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}