#include<algorithm>
#include<vector>

/*
COPY STUFF BELOW THIS COMMENT
*/

#pragma region

class max_flow_graph_copy {
public:
	max_flow_graph_copy(int);
	~max_flow_graph_copy();

	void reset(); //deletes everything
	void resize(int); //deletes everything and resizes the max_flow_graph_copy
	void add_edge(int, int, int);
	void add_double_edge(int, int, int);
	int max_flow(int, int);
	int size();
protected:
	int *head, *gap, *lvl;
	int isize;
	struct edge {
		int v, c, n;
		edge();
		edge(int, int, int);
	};
	std::vector<edge> edges;
private:
	int sap(int, int, int, int);
};


max_flow_graph_copy::max_flow_graph_copy(int size) {
	isize = size;
	head = new int[size];
	gap = new int[size];
	lvl = new int[size];
	std::fill(head, head + size, -1);
}

void max_flow_graph_copy::reset() {
	std::fill(head, head + isize, -1);
	edges.clear();
}

int max_flow_graph_copy::size() {
	return isize;
}

void max_flow_graph_copy::resize(int size) {
	delete[] head;
	edges.clear();
	isize = size;

	head = new int[size];
	gap = new int[size];
	lvl = new int[size];
	std::fill(head, head + size, -1);
}

void max_flow_graph_copy::add_edge(int u, int v, int c) {
	if (u >= isize || v >= isize || c < 0) {
		throw std::invalid_argument("invalid argument");
		return;
	}

	edges.emplace_back(v, c, head[u]);
	head[u] = edges.size() - 1;

	edges.emplace_back(u, 0, head[v]);
	head[v] = edges.size() - 1;
}

void max_flow_graph_copy::add_double_edge(int u, int v, int c) {
	if (u >= isize || v >= isize || c < 0) {
		throw std::invalid_argument("invalid argument");
		return;
	}

	edges.emplace_back(v, c, head[u]);
	head[u] = edges.size() - 1;

	edges.emplace_back(u, c, head[v]);
	head[v] = edges.size() - 1;
}

int max_flow_graph_copy::sap(int pos, int flow, int source, int sink) {
	if (pos == sink) {
		return flow;
	}
	int flow_left = flow;
	for (int a = head[pos]; a != -1; a = edges[a].n) {
		if (edges[a].c && lvl[edges[a].v] + 1 == lvl[pos]) {
			int cf = sap(edges[a].v, std::min(edges[a].c, flow_left), source, sink);

			flow_left -= cf;
			edges[a].c -= cf;
			edges[a ^ 1].c += cf;

			if (lvl[source] == isize || flow_left == 0) {
				return flow - flow_left;
			}
		}
	}


	if (flow == flow_left) {
		gap[lvl[pos]]--;
		if (gap[lvl[pos]] == 0) {
			lvl[source] = isize;
		} else {
			int min_child = isize;
			for (int a = head[pos]; a != -1; a = edges[a].n) {
				if (edges[a].c) {
					min_child = std::min(min_child, lvl[edges[a].v]);
				}
			}
			lvl[pos] = min_child + 1;
			gap[lvl[pos]]++;
		}
	}
	return flow - flow_left;
}

int max_flow_graph_copy::max_flow(int source, int sink) {
	std::fill(lvl, gap + isize, 0);
	std::fill(lvl, lvl + isize, 0);
	gap[0] = isize;

	int ret = 0;
	while (lvl[source] < isize) {
		ret += sap(source, std::numeric_limits<int>::max(), source, sink); //idk why this even exists
	}
	return ret;
}

max_flow_graph_copy::~max_flow_graph_copy() {
	delete[] head;
	delete[] lvl;
	delete[] gap;
}

max_flow_graph_copy::edge::edge() {}
max_flow_graph_copy::edge::edge(int x, int y, int z) {
	v = x;
	c = y;
	n = z;
}


#pragma endregion