UVa 11974 - Switch The Lights

//UVa 11974 - Switch The Lights

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

int swtch[100];

int main() {
	int cases;
	scanf("%d", &cases);
	for (int cas = 1; cas <= cases; cas++) {
		int n, m;
		scanf("%d %d", &n, &m);

		int nxt = 0, now = 1, end = (1 << n) - 1;
		vector<int> level[2];
		bool seen[32768] = { false };

		for (int i = 0; i < m; i++) {
			swtch[i] = 0;
			for (int j = 0; j < n; j++) {
				int bit;
				scanf("%d", &bit);
				swtch[i] = (swtch[i] << 1) | bit;
			}
			level[nxt].push_back(swtch[i]);
			seen[swtch[i]] = true;
		}

		if (m <= 0) {
			printf("Case %d: 0\n", cas);
			continue;
		}

		int lvl = 1;
		bool found = seen[end];
		while (!seen[end] && !level[nxt].empty()) {
			lvl++;
			now = nxt;
			nxt = nxt ^ 1;
			level[nxt].clear();
			for (int i = 0; i < m; i++) {
				for (vector<int>::const_iterator I = level[now].begin(); I != level[now].end(); I++) {
					int generated = (*I) ^ swtch[i];
					if (generated == end) {
						found = true;
						break;
					}
					if (!seen[generated]) {
						level[nxt].push_back(generated);
						seen[generated] = true;
					}
				}
				if (found)
					break;
			}
			if (found)
				break;
		}

		if (found)
			printf("Case %d: %d\n", cas, lvl);
		else
			printf("Case %d: IMPOSSIBLE\n", cas);
	}
	return 0;
}