【題意】：你是一個獵人，這里有n(n <= 21)棵樹和一只猴子，你想獵殺這只猴子，但你不知道這只猴子具體在哪棵樹上。每一次你可以隨便射擊一棵樹，如果猴子在這課樹上就會被殺掉。如果猴子不在這棵樹上，他一定會跳到與當前所處的樹相鄰的其他樹。給出樹與樹之間的相鄰關系，問獵殺這只猴子的最少開槍數是多少，并輸出射擊的方案，如果存在多組相等開槍數的方案則輸出字典序最小的那一組。

【題解】：非常好的搜索題！剛開始以為是個博弈的東西，后來一直推不到最優決策，意識到數據有這么少，應該可以搜索過去。
              因為n小于等于21，可以采用狀態壓縮。對于猴子可能在的某些棵樹標記為1，否則標記為0，最終狀態為全0，即0.
              猴子從當前的樹跳到相鄰的樹這個要先預處理，以后每次可以用O(n)的時間復雜度轉移狀態。
              不可能存在猴子的樹是不用管的，這里可以剪枝；如果m > n - 1即關系中存在環則一定無解。

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "queue"
 5 #include "string"
 6 using namespace std;
 7 int n, m;
 8 bool visit[1<<22];
 9 int edge[22];
10 string ans;
11 struct Node {
12     int mask;
13     string path;
14     Node(){}
15     Node(int _mask, string _path) {
16         mask = _mask, path = _path;
17     }
18 };
19 
20 bool bfs() {
21     queue<Node> que;
22     memset(visit, false, sizeof(visit));
23     que.push(Node((1 << n) - 1, ""));
24     visit[(1<<n)-1] = true;
25     while(!que.empty()) {
26         Node now = que.front();
27         que.pop();
28         for(int i = 0; i < n; i++) {
29             if(now.mask & (1 << i)) {
30                 int mask = now.mask ^ (1 << i);
31                 int newmask = 0;
32                 for(int j = 0; j < n; j++)
33                     if(mask & (1 << j)) newmask |= edge[j];
34                 if(visit[newmask]) continue;
35                 visit[newmask] = true;
36                 char ch = i + '0';
37                 string tmp = now.path + ch;
38                 if(newmask == 0) {
39                     ans = tmp;
40                     return true;
41                 }
42                 que.push(Node(newmask, tmp));
43             }
44         }
45     }
46     return false;
47 }
48 
49 void solve() {
50     if((m > n - 1) || !bfs()) printf("Impossible\n");
51     else {
52         printf("%d:", ans.length());
53         for(int i = 0; i < ans.length(); i++) printf(" %d", ans[i] - '0');
54         printf("\n");
55     }
56     return;
57 }
58 
59 int main() {
60     while(~scanf("%d%d", &n, &m)) {
61         if(!n && !m) break;
62         memset(edge, 0, sizeof(edge));
63         for(int i = 0; i < m; i++) {
64             int u, v;
65             scanf("%d%d", &u, &v);
66             edge[u] |= (1 << v), edge[v] |= (1 << u);
67         }
68         solve();
69     }
70     return 0;
71 }