1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 using namespace std;
 5 #define maxn 1000
 6 #define maxm 500000
 7 const int inf = 1 << 30;
 8 int s, t, n, m;
 9 int eh[maxn], low[maxn], dist[maxn], cnt[maxn], tot, pre[maxn], cur[maxn];
10 bool color[maxn];
11 struct Edge {
12     int u, v, cap, flow, next;
13 }et[maxm];
14 
15 void init() {
16     tot = 0;
17     memset(eh, -1, sizeof(eh));
18 }
19 
20 void add(int u, int v, int cap, int flow) {
21     Edge e = {u, v, cap, flow, eh[u]};
22     et[tot] = e;
23     eh[u] = tot++;
24 }
25 
26 void addedge(int u, int v, int cap) {
27     add(u, v, cap, 0), add(v, u, 0, 0);
28 }
29 
30 int isap(int s, int t, int n) {
31     int u, v, now, flow = 0;
32     memset(low, 0, sizeof(low));
33     memset(cnt, 0, sizeof(cnt));
34     memset(dist, 0, sizeof(dist));
35     for(u = 0; u <= n; u++) cur[u] = eh[u];
36     low[s] = inf, cnt[0] = n;
37     u = s;
38     while(dist[s] < n) {
39         for(now = cur[u]; now != -1; now = et[now].next)
40             if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1) break;
41         if(now != -1) {
42             cur[u] = pre[v] = now;
43             low[v] = min(low[u], et[now].cap - et[now].flow);
44             u = v;
45             if(u == t) {
46                 for(; u != s; u = et[pre[u]].u) {
47                     et[pre[u]].flow += low[t];
48                     et[pre[u]^1].flow -= low[t];
49                 }
50                 low[s] = inf, flow += low[t];
51             }
52         } else {
53             if(--cnt[dist[u]] == 0) break;
54             dist[u] = n;
55             cur[u] = eh[u];
56             for(now = eh[u]; now != -1; now = et[now].next)
57                 if(et[now].cap - et[now].flow && dist[u] > dist[v = et[now].v] + 1)
58                     dist[u] = dist[v] + 1;
59             cnt[dist[u]]++;
60             if(u != s) u = et[pre[u]].u;
61         }
62     }
63     return flow;
64 }
65 
66 void dfs(int u) {
67     color[u] = 1;
68     for(int i = eh[u]; i != -1; i = et[i].next)
69         if(!color[et[i].v] && et[i].cap - et[i].flow) 
70             dfs(et[i].v);
71 }
72 
73 int main() {
74     int T;
75     scanf("%d", &T);
76     for(int tt = 1; tt <= T; tt++) {
77         scanf("%d%d", &n, &m);
78         init();
79         s = 0, t = n - 1;
80         for(int i = 0; i < m; i++) {
81             int u, v, cap, d;
82             scanf("%d%d%d%d", &u, &v, &cap, &d);
83             if(d) addedge(u, v, cap), addedge(v, u, cap);
84             else addedge(u, v, cap);
85         }
86         isap(s, t, n);
87         for(int i = 0; i < tot; i += 2) {
88             if(et[i].cap == et[i].flow) et[i].cap = 1, et[i].flow = 0;
89             else et[i].flow = 0;
90             et[i^1].cap = et[i^1].flow = 0;
91         }
92         int ans = isap(s, t, n);
93         printf("Case %d: %d\n", tt, ans);
94     }
95 }
96