游河

Time Limit: 1000 MS

Memory Limit: 65535 K

Total Submit: 71(14 users)

Total Accepted: 41(14 users)

Special Judge: No

Description

     假期，Hrbust集训队在Tang长老的带领下去河上坐船游玩。 但是很多队员想单独坐船游览风光，体验一个人的旅行。 但是教主说那样会很危险，而且似乎也没那么多的旅行路线。可是队员们还是坚持自己的想法，于是教主提了个要求：如果游览的路线足够一人一条，而且每条路线没有重复的水路的话，就同意大家的做法，不然，Tang长老就请大家集体吃冰棍，一起坐船去。

集训队这次一共去了 D 个人，（1<=D<=200），已知河道上一共N个河叉（2<=N<=200），大家都是从1号位置开始旅行的，终点为第 N 号位置，现在已知道在这N个位置之间有 M 条连通的水路(2<=M<=40000)。

请帮大家计算下存在的路线数是否够大家单人旅行的。

Input

Line 1: 河叉总数 N，道路总数 M，集训队人数 D。

Line 2...M+1:两个整数 A,B，表示位置 A 和 B 之间有一条直接连通的水路。

Output

Line1:如果存在的路径数够大家单人旅行(路径数>= D),输出“Orz!”,否则输出“Jiao Zhu v5!”。

  

Sample Input

2 2 1

1 2

1 2

7 9 5

1 2

2 3

3 7

1 4

4 3

4 5

5 7

1 6

6 7

 

Sample Output

Orz!

Jiao Zhu v5!

Hint

注意是边是双向的。

第一组样例：

 

 

从 1 到 2 有两条没有重复道路的路径。

第二组样例：

 

 

从 1 到 7 有三条符合条件的路径：

1 - 2 - 3 - 7

1 - 4 - 5 -7

1 - 6 - 7

 

1 #include 
          
             2 #include 
           
              3 #include 
            
               4 #include 
             
                5 #include 
              
                 6 using namespace std;  7 #define M 210  8 #define INF 100000  9 struct Arc 10 { 11     int c,f; 12 }edge[M][M]; 13 int n,m; 14 int flag[M],prev[M]; 15 int alpha[M],queue[M]; 16 int v,qs,qe; 17 int ford() 18 { 19     while(1) 20     { 21         memset(flag,-1,sizeof(flag)); 22         memset(prev,-1,sizeof(prev)); 23         memset(alpha,-1,sizeof(alpha)); 24         flag[0]=prev[0]=0; 25         alpha[0]=INF; 26         qs=qe=0; 27         queue[qe++]=0; 28         while(qs
               
                0) 42 { 43 flag[i]=0;prev[i]=-v; 44 alpha[i]=min(alpha[v],edge[v][i].f); 45 queue[qe++]=i; 46 } 47 } 48 } 49 flag[v]=1; 50 } 51 if(flag[n-1]==-1||alpha[n-1]==0) break; 52 int k1=n-1,k2=fabs(prev[k1]); 53 int a=alpha[n-1]; 54 while(1) 55 { 56 if(edge[k2][k1].f
                
                 =cc) 98 printf("Orz!\n"); 99 else100 printf("Jiao Zhu v5!\n");101 }102 }