SWERC 2010: Jumping Monkey [Solved]

As you can find on my previous post, I was getting wrong answer on this problem. Thanks to BearedCrazyCoder aka Sidky for pointing out the mistake in my approach. I was using dynamic programming and moving from one state to the other recursively. You can read this comment for understanding the flaw  -

btw, I don't think you can solve this in this approach, because, in this approach, the nodes will be discovered in depth-first order.
Let's say, the nodes are discovered in this order:
v1 v2 v3 v4 v5 v6 v7 ... vp .. vq
Let's say, vq has only one next state, vp.
So, dp[vp] = INF
Now, let's assume, it is possible to reach vp in a shorter path:
v1 v2' v3' ... vq
now, it can visit vp, but since dp[vq] has already been calculated as INF, it will not proceed any further. So, this may lead to a suboptimal solution (or probably no solution)

So I resorted to good old Breadth First Search and my program got accepted in 4.678 seconds which was worst among others. I tried to optimize it in all possible ways (except for IO optimization). The run times and tweaks in my next submissions were -

Runtime	Optimizations
4.100	Stopped shooting at positions where there is no monkey
1.570	Converted the vector to simple array
0.709	Converted all the data types to the most efficient possible [integers to chars for index variables, result array etc.]
0.693	Converting the most used variables to register
0.723	At this stage I tried to pre-compute for each integer the positions where it has a '1' bit and store those positions in an array. This really backfired in spite of reduction in loop instructions as array indexing was increased
0.281	Here, I've observed that I can remove one inner loop. Instead of shooting one tree at a time, I can shoot all the tree at once and later remove the effect of an particular tree to get the state for that tree

One important note, I've found that even on a tree (the graph is tree), it is sometimes not possible to kill the monkey. I can't think such a case. Can you find any?

Here's my final source code -

/*
Problem Name : Jumping Monkey
Problem Number : Live Archive 4959
Link : http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4959
Problem Type : BFS, Optimization
Difficulty : 7 / 10
Interest : 8 / 10
Complexity : O(N*2^N)
Date : November 29, 2010
*/
#include<vector>
#include<cstdio>
#include<cassert>
using namespace std;

#define MAXN 21
#define INF 10234567
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define rep(i,n) for(i=0;i<(n);i++)

char d[(1<<MAXN)]; //distance array...final output
int pre[(1<<MAXN)];
char shoot[(1<<MAXN)];
char n;
int m;
int Q[(1<<MAXN)];
char adj[MAXN+2][MAXN+2];//adjacency list in array form
char ct[MAXN+2]; // counter for adjacency list

//4.678 -> 4.100 -> 1.570 -> .709-> .693 -> .723 -> 0.281

char counter[MAXN+2];

int bfs() {
 register int sz = 0, cur = 0;
 register char i,j;
 register int st, nstate, cur_state;
 Q[sz++] = (1<<n) - 1;
 memset(d,-1,sizeof(d));
 d[(1<<n)-1] = 0;
 while(cur < sz) {
  st = Q[cur++];
  memset(counter,0,sizeof(counter));
  cur_state = 0;
  rep(i,n) if(st & (1<<i)) {
   rep(j,ct[i]) {
    counter[adj[i][j]]++;
    cur_state |= (1<<adj[i][j]);
   }
  }
  rep(i,n) if(st & (1<<i)) {
   nstate = cur_state;
   rep(j,ct[i]) {
    if(counter[adj[i][j]]-1<=0) nstate &= ~(1<<adj[i][j]);
   }
   if(d[nstate] == -1) {
    d[nstate] = d[st] + 1;
    Q[sz++] = nstate;
    pre[nstate] = st;
    shoot[nstate] = i;
    if(nstate == 0) return d[nstate];
   }
  }
 }
 return INF;
}

void print(int st) {
 if(st == (1<<n)-1) return;
 print(pre[st]);
 printf(" %d",shoot[st]);
}

int main()
{
 int i;
 int a,b;
 int ret;
 while(scanf(" %d %d",&n,&m)==2) {
  if(n == 0 && m == 0) break;
  memset(adj,0,sizeof(adj));
  rep(i,n) ct[i] = 0;
  rep(i,m) {
   scanf(" %d %d",&a,&b);
   adj[a][ct[a]++] = b;
   adj[b][ct[b]++] = a;
  }
  if(m != n-1) { printf("Impossible\n"); continue; }
  ret = bfs();
  if(ret == INF) { printf("Impossible\n"); continue; }
  printf("%d:",ret);
  print(0); printf("\n");
 }
 return 0;
}