uva_208

/*
 Author                             :     unlucky_13
 Problem_link                       :
 Category                           :
 Algorithm_Used                     :Bactracking _ The main optimaization comes from floyed marshell if there is no path of any lenght from u to n(~dis[u][n]=0) we won't follow the path beacuse this will give no solution

 */

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#define LL long long int
//const long long int inf = 2147483647 ;
//const int minx=;
const int maxn=30;

using namespace std;
int n ,adj[maxn][maxn],path[maxn],taken[maxn],res,dis[maxn][maxn];

void FW(){


    for(int k=0;k<21;k++){
        for(int i=0;i<21;i++){
            for(int j=0;j<21;j++){
                dis[i][j] = dis[i][j]||(dis[i][k] && dis[k][j]) ;
            }
        }
    }

    /*for(int i=0;i<21;i++){
        for(int j=0;j<21;j++) printf("%d ",dis[i][j]) ;

    }*/
}




void BT(int u,int len){
    if(u==n){
        res++ ;
        printf("1") ;
        for(int i=0;i<len;i++) printf(" %d",path[i]) ;
        printf("\n") ;
    }
    else if(dis[u][n]){
        for(int i=0;i<21;i++){
            if(adj[u][i] && taken[i]==0){
                taken[i] = 1 ;
                path[len]=i ;
                BT(i,len+1) ;
                taken[i]=0 ;
            }
        }
    }
}

int main() {

    int x,y,ct=1;
    freopen("C:\\Users\\Mazhar\\Desktop\\in.txt", "r", stdin);
    while(scanf("%d",&n)==1){
        printf("CASE %d:\n",ct++) ;
        res = 0 ;
        memset(adj,0,sizeof(adj)) ;
        memset(dis,0,sizeof(dis)) ;
        while(1){
            scanf("%d %d",&x,&y) ;
            dis[x][y]=dis[y][x] = adj[x][y]=adj[y][x]=1 ;

            if(x==0 && y==0) break ;
        }
        memset(taken,0,sizeof(taken)) ;
        FW() ;
        taken[1]=1 ;
        BT(1,0) ;
        printf("There are %d routes from the firestation to streetcorner %d.\n",res,n) ;


    }

    return 0;
}