1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn = 30; 7  8 int t, cnt, num, G[maxn][maxn], vis[maxn], mark[maxn]; 9 10 void build() {11     memset(G, 0, sizeof(G));12     int u, v; cnt = 1;13     while (scanf("%d%d", &u, &v) == 2 && u) {14         G[u][v] = 1;15         G[v][u] = 1;16         if (u > cnt) cnt = u;17         if (v > cnt) cnt = v;18     }19 }20 21 void judge(int n) {22     mark[n] = 1;23     for (int i = 1; i <= cnt; i++)24         if (G[n][i] && !mark[i]) judge(i);25 }26 27 void print_ans() {28     num++;29     printf("%d", 1);30     for (int step = 2; step <= vis[t]; step++)31         for (int pos = 2; pos <= cnt; pos++)32             if (vis[pos] == step) printf(" %d", pos);33     printf("\n");34 }35 36 void dfs(int u) {37     if (u == t) print_ans();38     else {39         for (int v = 2; v <= cnt; v++)40             if (G[u][v] && !vis[v] && mark[v]) {41                 vis[v] = vis[u] + 1;42                 dfs(v);43                 vis[v] = 0;44             }45     }46 }47 48 int main() {49     int kase = 0;50     while (scanf("%d", &t) == 1) {51         build();52         printf("CASE %d:\n", ++kase);53         memset(mark, 0, sizeof(mark));54         judge(t);55         num = 0, vis[1] = 1;56         dfs(1);57         printf("There are %d routes from the firestation to streetcorner %d.\n", num, t);58     }59     return 0;60 }