假期，Hrbust集训队在Tang长老的带领下去河上坐船游玩。 但是很多队员想单独坐船游览风光，体验一个人的旅行。 但是教主说那样会很危险，而且似乎也没那么多的旅行路线。可是队员们还是坚持自己的想法，于是教主提了个要求：如果游览的路线足够一人一条，而且每条路线没有重复的水路的话，就同意大家的做法，不然，Tang长老就请大家集体吃冰棍，一起坐船去。
集训队这次一共去了 D 个人，（1<=D<=200），已知河道上一共N个河叉（2<=N<=200），大家都是从1号位置开始旅行的，终点为第 N 号位置，现在已知道在这N个位置之间有 M 条连通的水路(2<=M<=40000)。
请帮大家计算下存在的路线数是否够大家单人旅行的。
InputLine 1: 河叉总数 N，道路总数 M，集训队人数 D。
Line 2...M+1:两个整数 A,B，表示位置 A 和 B 之间有一条直接连通的水路。
OutputLine1:如果存在的路径数够大家单人旅行(路径数>= 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
#include<bits/stdc++.h> using namespace std; #define mms(x, y) memset(x, y, sizeof x) const int MAX = 2e4 + 7; const int INF = 0x3f3f3f3f; struct node { int to, c, next; } e[MAX * 20]; int lev[MAX]; int head[MAX]; int n, m, k, num, S, T; void init() { mms(head, -1); num = 0; S = 1; T = n; } void add(int x, int y, int z) { e[num] = {y, z, head[x]}; head[x] = num++; swap(x, y); e[num] = {y, z, head[x]}; head[x] = num++; } bool bfs() { queue <int> q; q.push(S); mms(lev, 0); lev[S] = 1; while(!q.empty()) { int u = q.front(); if(u == T) return 1; q.pop(); for(int i = head[u]; i != -1; i = e[i].next) { int v = e[i].to; int w = e[i].c; if(w && lev[v] == 0) { lev[v] = lev[u] + 1; q.push(v); } } } return 0; } int dfs(int u, int maxflow) { if(u == T) return maxflow; int ans = 0; for(int i = head[u]; i != -1; i = e[i].next) { int v = e[i].to; int w = e[i].c; if(lev[v] == lev[u] + 1 && w) { int f = dfs(v, min(maxflow - ans, w)); e[i].c -= f; e[i ^ 1].c += f; ans += f; if(ans == maxflow) return ans; } } return ans; } void dinic() { int ans = 0; while(bfs()) ans += dfs(S, INF); if(ans >= k) cout << "Orz!" << endl; else cout << "Jiao Zhu v5!" << endl; } int main() { ios::sync_with_stdio(false); while(cin >> n >> m >> k) { init(); for(int i = 0, x, y; i < m; i++) { cin >> x >> y; add(x, y, 1); } dinic(); } return 0; }