//208 Firetruck
//https://u...content-available-to-author-only...e.org/external/2/208.pdf
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 22
#define MAXNODE 100
#define INFINITY 32767
int addj[MAXNODE][MAXNODE];
int visited[MAXNODE][MAXNODE];
int path[1000];
int trout = 0;
int vist[MAXNODE];
int dist[MAXNODE][MAXNODE];
void init()
{
for (int i = 0; i <= MAXNODE; i++)
{
path[i] = 0;
vist[i] = 0;
for (int j = 0; j <= MAXNODE; j++)
{
addj[i][j] = visited[i][j] = 0;
dist[i][j] = INFINITY;
}
}
}
void foloyd_warshal(int maxnode)
{
for (int i = 0; i <= maxnode; i++)
{
dist[i][i] = 0;
}
for (int k = 0; k <= maxnode; k++)
{
for (int i = 0; i <= maxnode; i++)
{
for (int j = 0; j <= maxnode; j++)
{
if (dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
void find_rout(int node,int firecorner,int maxnode,int index)
{
int np = 0;
if (node == firecorner)
{
//printf(" ");
int i = 0;
for (i = 0; i < index-1; i++)
printf("%d ",path[i]);
printf("%d", path[i]);
printf("\n");
trout++;
return ;
}
for (int v = 0; v <= maxnode; v++)
{
if (((addj[node][v]) && (!vist[v])) && (dist[firecorner][v]<INFINITY))
{
visited[node][v] = 1;
path[index] = v;
np = v;
vist[v] = 1;
find_rout(np, firecorner, maxnode, index + 1);
vist[np] = 0;
/*if (np>2)
vist[np] = 0;*/
}
}
}
int main()
{
int firecorner = 0,case1=1;
int u, v,maxnode;
/*freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);*/
while (scanf("%d", &firecorner) != EOF)
{
maxnode = 0;
trout = 0;
init();
while (1)
{
scanf("%d %d", &u, &v);
if (u == 0 && v == 0)
break;
addj[u][v] = 1;
addj[v][u] = 1;
dist[u][v] = 1;
dist[v][u] = 1;
if (maxnode < u)
maxnode = u;
if (maxnode < v)
maxnode = v;
}
foloyd_warshal(maxnode);
path[0] = 1;
vist[1] = 1;
printf("CASE %d:\n", case1++);
find_rout(1, firecorner,maxnode,1);
printf("There are %d routes from the firestation to streetcorner %d.\n", trout,firecorner);
}
return 0;
}
Ly8yMDggRmlyZXRydWNrCi8vaHR0cHM6Ly91Li4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5lLm9yZy9leHRlcm5hbC8yLzIwOC5wZGYKCiNkZWZpbmUgX0NSVF9TRUNVUkVfTk9fV0FSTklOR1MKCiNpbmNsdWRlPHN0ZGlvLmg+CgojZGVmaW5lIE1BWCAyMgojZGVmaW5lIE1BWE5PREUgMTAwCiNkZWZpbmUgSU5GSU5JVFkgMzI3NjcKCmludCBhZGRqW01BWE5PREVdW01BWE5PREVdOwppbnQgdmlzaXRlZFtNQVhOT0RFXVtNQVhOT0RFXTsKaW50IHBhdGhbMTAwMF07CmludCB0cm91dCA9IDA7CmludCB2aXN0W01BWE5PREVdOwppbnQgZGlzdFtNQVhOT0RFXVtNQVhOT0RFXTsKdm9pZCBpbml0KCkKewoJZm9yIChpbnQgaSA9IDA7IGkgPD0gTUFYTk9ERTsgaSsrKQoJewoJCXBhdGhbaV0gPSAwOwoJCXZpc3RbaV0gPSAwOwoJCWZvciAoaW50IGogPSAwOyBqIDw9IE1BWE5PREU7IGorKykKCQl7CgkJCWFkZGpbaV1bal0gPSB2aXNpdGVkW2ldW2pdID0gMDsKCQkJZGlzdFtpXVtqXSA9IElORklOSVRZOwoJCX0KCgl9Cn0KCnZvaWQgZm9sb3lkX3dhcnNoYWwoaW50IG1heG5vZGUpCnsKCWZvciAoaW50IGkgPSAwOyBpIDw9IG1heG5vZGU7IGkrKykKCXsKCQlkaXN0W2ldW2ldID0gMDsKCX0KCglmb3IgKGludCBrID0gMDsgayA8PSBtYXhub2RlOyBrKyspCgl7CgkJZm9yIChpbnQgaSA9IDA7IGkgPD0gbWF4bm9kZTsgaSsrKQoJCXsKCQkJZm9yIChpbnQgaiA9IDA7IGogPD0gbWF4bm9kZTsgaisrKQoJCQl7CgkJCQlpZiAoZGlzdFtpXVtqXSA+IGRpc3RbaV1ba10gKyBkaXN0W2tdW2pdKQoJCQkJewoJCQkJCWRpc3RbaV1bal0gPSBkaXN0W2ldW2tdICsgZGlzdFtrXVtqXTsKCQkJCX0KCQkJfQoKCQl9Cgl9Cn0KCgoKCnZvaWQgZmluZF9yb3V0KGludCBub2RlLGludCBmaXJlY29ybmVyLGludCBtYXhub2RlLGludCBpbmRleCkKewoJaW50IG5wID0gMDsKCWlmIChub2RlID09IGZpcmVjb3JuZXIpCgl7CgkJLy9wcmludGYoIiAgICIpOwoJCWludCBpID0gMDsKCQlmb3IgKGkgPSAwOyBpIDwgaW5kZXgtMTsgaSsrKQoJCQlwcmludGYoIiVkICIscGF0aFtpXSk7CgkJcHJpbnRmKCIlZCIsIHBhdGhbaV0pOwoJCXByaW50ZigiXG4iKTsKCQl0cm91dCsrOwoJCXJldHVybiA7Cgl9Cglmb3IgKGludCB2ID0gMDsgdiA8PSBtYXhub2RlOyB2KyspCgl7CgkJaWYgKCgoYWRkaltub2RlXVt2XSkgJiYgKCF2aXN0W3ZdKSkgJiYgKGRpc3RbZmlyZWNvcm5lcl1bdl08SU5GSU5JVFkpKQoJCXsKCQkJdmlzaXRlZFtub2RlXVt2XSA9IDE7CgkJCXBhdGhbaW5kZXhdID0gdjsKCQkJbnAgPSB2OwoJCQl2aXN0W3ZdID0gMTsKCQkJZmluZF9yb3V0KG5wLCBmaXJlY29ybmVyLCBtYXhub2RlLCBpbmRleCArIDEpOwoJCQl2aXN0W25wXSA9IDA7CgkJCS8qaWYgKG5wPjIpCgkJCQl2aXN0W25wXSA9IDA7Ki8KCQl9Cgl9Cn0KCmludCBtYWluKCkKewoJaW50IGZpcmVjb3JuZXIgPSAwLGNhc2UxPTE7CglpbnQgdSwgdixtYXhub2RlOwoJLypmcmVvcGVuKCJpbi50eHQiLCJyIixzdGRpbik7CglmcmVvcGVuKCJvdXQudHh0IiwidyIsc3Rkb3V0KTsqLwoKCXdoaWxlIChzY2FuZigiJWQiLCAmZmlyZWNvcm5lcikgIT0gRU9GKQoJewoJCW1heG5vZGUgPSAwOwoJCXRyb3V0ID0gMDsKCQlpbml0KCk7CgkJd2hpbGUgKDEpCgkJewoJCQlzY2FuZigiJWQgJWQiLCAmdSwgJnYpOwoJCQlpZiAodSA9PSAwICYmIHYgPT0gMCkKCQkJCWJyZWFrOwoJCQlhZGRqW3VdW3ZdID0gMTsKCQkJYWRkalt2XVt1XSA9IDE7CgkJCWRpc3RbdV1bdl0gPSAxOwoJCQlkaXN0W3ZdW3VdID0gMTsKCQkJaWYgKG1heG5vZGUgPCB1KQoJCQkJbWF4bm9kZSA9IHU7CgkJCWlmIChtYXhub2RlIDwgdikKCQkJCW1heG5vZGUgPSB2OwoJCX0KCQlmb2xveWRfd2Fyc2hhbChtYXhub2RlKTsKCQlwYXRoWzBdID0gMTsKCQl2aXN0WzFdID0gMTsKCQlwcmludGYoIkNBU0UgJWQ6XG4iLCBjYXNlMSsrKTsKCQlmaW5kX3JvdXQoMSwgZmlyZWNvcm5lcixtYXhub2RlLDEpOwoJCXByaW50ZigiVGhlcmUgYXJlICVkIHJvdXRlcyBmcm9tIHRoZSBmaXJlc3RhdGlvbiB0byBzdHJlZXRjb3JuZXIgJWQuXG4iLCB0cm91dCxmaXJlY29ybmVyKTsKCX0KCglyZXR1cm4gMDsKfQ==