#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct edge {
	int from, to;
	int flow, cap;
};

const int INF = 1000 * 1000 * 1000;

vector <int> d;
vector <vector <int, int> > g;
vector <edge> e;
vector <int> ptr;
int n, t;

bool bfs1() {
	d.assign(n, -1);
	queue <int> q;
	d[0] = 0;
	q.push(0);
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (auto i : g[v]) {
			int to = e[i].to;
			if (e[i].flow < e[i].cap && d[to] == -1) {
				q.push(to);
				d[to] = d[v] + 1;
			}
		}
		
	}
	if (d[t] != -1)
			return 1;
		else
			return 0;
}

int dfs1(int v, int flow) {
	if (v == t)
		return flow;
	if (!flow)
		return 0;
	for (; ptr[v] < g[v].size(); ++ptr[v]) {
		int p = g[v][ptr[v]];
		int to = e[p].to;
		if (d[to] == d[v] + 1) {
			int MAX_FLOW = dfs1(to, min(flow, e[p].cap - e[p].flow));
			if (MAX_FLOW) {
				e[p].flow += MAX_FLOW;
				e[p ^ 1].flow -= MAX_FLOW;
				return MAX_FLOW;
			}
		}
	}

	return 0;
}

int dinic() {
	int ans = 0;
	while (bfs1()) {
		ptr.assign(n, 0);
		//int k = dfs(0, 1000*1000);

	}

	return ans;
}

int main() {
	return 0;
}