Dinic 1 #include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define MAXN 110
struct Edge{
int from, to, cap, flow;
};
bool comp(const Edge& a, const Edge& b){
return a.from < b.from || (a.from == b.from && a.to < b.to);
}
struct Dinic{
int n, m, s, t;
vector<Edge> edges;
vector<int> G[MAXN];
bool vis[MAXN];
int d[MAXN];
int cur[MAXN];
void init(int n){
this->n = n;
for (int i = ; i <= n; i++)
G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, int cap){
edges.push_back(Edge{ from, to, cap, });
edges.push_back(Edge{ to, from, , });
m = edges.size();
G[from].push_back(m - );
G[to].push_back(m - );
}
bool BFS(){
memset(vis, , sizeof(vis));
queue<int> Q;
Q.push(s);
d[s] = ;
vis[s] = ;
while (!Q.empty()){
int x = Q.front();
Q.pop();
for (int i = ; i<G[x].size(); i++){
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap>e.flow){
vis[e.to] = ;
d[e.to] = d[x] + ;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x, int a){
if (x == t || a == )return a;
int flow = , f;
for (int& i = cur[x]; i<G[x].size(); i++){
Edge& e = edges[G[x][i]];
if (d[x] + == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow)))>){
e.flow += f;
edges[G[x][i] ^ ].flow -= f;
flow += f;
a -= f;
if (a == )break;
}
}
return flow;
}
int Maxflow(int s, int t, int need){
this->s = s; this->t = t;
int flow = ;
while (BFS()){
memset(cur, , sizeof(cur));
flow += DFS(s, INF);
if (flow > need)return flow;
}
return flow;
}
//最小割割边
vector<int> Mincut(){
BFS();
vector<int> ans;
for (int i = ; i<edges.size(); i++){
Edge& e = edges[i];
if (vis[e.from] && !vis[e.to] && e.cap>)ans.push_back(i);
}
return ans;
}
void Reduce(){
for (int i = ; i < edges.size(); i++) edges[i].cap -= edges[i].flow;
}
void ClearFlow(){
for (int i = ; i < edges.size(); i++) edges[i].flow = ;
}
};
Dinic ex;
int main(){
int N, E, C, cas = ;
while (~scanf("%d%d%d", &N, &E, &C))
{
if (!N)break;
ex.init(N);
int a, b, c;
while (E--)
{
scanf("%d%d%d", &a, &b, &c);
ex.AddEdge(a, b, c);
}
int flow = ex.Maxflow(, N, INF);
printf("Case %d: ", ++cas);
if (flow > C)printf("possible\n");
else{
vector<int> cut = ex.Mincut();
ex.Reduce();
vector<Edge>ans;
for (int i = ; i < cut.size(); i++){
Edge& e = ex.edges[cut[i]];
int temp = e.cap;
e.cap = C;
ex.ClearFlow();
if (flow + ex.Maxflow(, N, C - flow) >= C)ans.push_back(e);
e.cap = temp;
}
if (ans.empty())printf("not possible\n");
else{
sort(ans.begin(), ans.end(), comp);
printf("possible option:(%d,%d)", ans[].from, ans[].to);
for (int i = ; i < ans.size(); i++)
printf(",(%d,%d)", ans[i].from, ans[i].to);
printf("\n");
}
}
}
return ;
}