- #include<bits/stdc++.h>
- #define ms(x) memset(x,0,sizeof(x))
- using namespace std;
- const int inf = 1000000000;
- const int maxn = 104100;
- const int maxm = 108100;
- struct Edge
- {
- int v, f, nxt;
- };
- int src, sink;
- int g[maxn + 10];
- int nume;
- int l, r;
- int n, m, k, step = 0;
- Edge e[maxm * 2 + 10];
- void addedge(int u, int v, int c)
- {
- e[++nume].v = v;
- e[nume].f = c;
- e[nume].nxt = g[u];
- g[u] = nume;
- e[++nume].v = u;
- e[nume].f = 0;
- e[nume].nxt = g[v];
- g[v] = nume;
- }
- void init()
- {
- ms(g);
- nume = 1;
- }
- int x, y;
- queue<int>que;
- bool vis[maxn+10];
- int dist[maxn+10];
- void bfs()
- {
- ms(dist);
- while(!que.empty()) que.pop();
- vis[src] = true;
- que.push(src);
- while(!que.empty())
- {
- int u = que.front();
- que.pop();
- for(int i=g[u]; i; i=e[i].nxt)
- {
- if(e[i].f && !vis[e[i].v])
- {
- que.push(e[i].v);
- dist[e[i].v] = dist[u] + 1;
- vis[e[i].v] = true;
- }
- }
- }
- }
- int dfs(int u, int delta)
- {
- if(u == sink)
- {
- return delta;
- }
- else
- {
- int ret = 0;
- for(int i=g[u]; delta && i; i = e[i].nxt)
- {
- if(e[i].f && dist[e[i].v] == dist[u] + 1)
- {
- int dd = dfs(e[i].v, min(e[i].f, delta));
- e[i].f -= dd;
- e[i^1].f += dd;
- delta -= dd;
- ret += dd;
- }
- }
- return ret;
- }
- }
- int maxflow()
- {
- int ret = 0;
- while(true)
- {
- ms(vis);
- bfs();
- if(!vis[sink]) return ret;
- ret += dfs(src, inf);
- }
- }
- int nn,mm;
- bool lowbound_flow()
- {
- init();
- int s =n+m+1,t = n+m+2;
- for(int i=0; i<k; i++)
- {
- scanf("%d%d",&x,&y);
- addedge(x,n+y,r-l);
- }
- addedge(t,s,inf);
- int S = n+m+3,T = n+m+4;
- for(int i=1; i<=n; i++)
- {
- //addedge(s,i,r-l);
- addedge(S,i,l);
- addedge(i,T,l);
- }
- for(int i=1; i<=m; i++)
- {
- //addedge(n+i,t,r-l);
- addedge(S,i,l);
- addedge(n+i,T,l);
- }
- src = S;
- sink = T;
- int ans = maxflow();
- if(ans == l*(n+m) )
- return 1;
- else return 0;
- }
- vector<int>u, v, L, U;
- int main()
- {
- while(scanf("%d%d%d",&n,&m,&k)!=EOF)
- {
- scanf("%d%d",&l,&r);
- printf("Case %d: ",++step);
- if(lowbound_flow()) puts("Yes");
- else puts("No");
- }
- return 0;
- }