#include<iostream>
#include<queue>
#include<limits.h>
#include<vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cassert>
#include <optional>

using namespace std;

using MaxFlow = int;
using VertexId = int;

void fulkerson(map<VertexId, vector<pair<VertexId, MaxFlow>>> graph)
{
	using Flow = int;

	VertexId maxInd = max_element(graph.cbegin(), graph.cend(), [](auto x, auto y)
	{
		return x.first < y.first;
	})->first;

	map<VertexId, vector<pair<VertexId, Flow>>> flowInGraph;
	for (auto const&[vertId, edges] : graph)
	{
		vector<pair<VertexId, Flow>> flow;
		for (auto& edge : edges)
		{
			flow.push_back({edge.first,Flow{0}});
		}
		flowInGraph[vertId] = flow;
	}

	vector<VertexId> chain;
	bool found = false;
	auto recurseSearch = [&](VertexId id, auto recurse)
	{
		if (id == maxInd)
		{
			found = true;
			return;
		}

		for (auto& nextVertflowToNext : flowInGraph[id])
		{
			auto nextVert = nextVertflowToNext.first;
			auto flowToNext = nextVertflowToNext.second;

			MaxFlow maxFlow;
			auto find = find_if(graph[id].cbegin(), graph[id].cend(), [&](pair<VertexId, MaxFlow> x)
			{
				return x.first == nextVert;
			});
			assert(find != graph[id].cend());
			maxFlow = find->second;

			if (flowToNext < maxFlow)
			{
				recurse(nextVert, recurse);
				if (found)
				{
					chain.push_back(nextVert);
					return;
				}
			}
		}
	};
	recurseSearch(VertexId{1}, recurseSearch);
	reverse(chain.begin(), chain.end());

	// find min flow
	//VertexId curr = 1;
	//for (auto next : chain)
	//{
	//	auto find = find_if(graph[id].cbegin(), graph[id].cend(), [&](pair<VertexId, MaxFlow> x)
	//	{
	//		return x.first == nextVert;
	//	});
	//	assert(find != graph[id].cend());
	//
	//
	//}

	for (auto i : chain)
		cout << " " << i << " ";
}

//int main()
//{
	//map<VertexId, vector<pair<VertexId, MaxFlow>>> graph;
	//graph[1] = {{2,1},{4,4}};
	//graph[2] = {{3,2},{5,3},{4,2}};
	//graph[3] = {{6,2}};
	//graph[4] = {{3,3}};
	//graph[5] = {{6,1}};
	//graph[6] = {};
	//
	//fulkerson(graph);

//constexpr int nodes = 6;
//
//int mat[nodes][nodes] = {
//	{0, 1, 0, 4, 0, 0},
//	{0, 0, 2, 2, 3, 0},
//	{0, 0, 0, 0, 0, 2},
//	{0, 0, 3, 0, 0, 0},
//	{0, 0, 0, 0, 0, 1},
//	{0, 0, 0, 0, 0, 0}
//};
//cout << "Max flow = " << ford_fulkerson_compute<nodes>(mat, 0, 5) << endl;
//return 0;
//}

constexpr int V = 6;

/* Returns true if there is a path from source 's' to sink 't' in
  residual graph. Also fills parent[] to store the path */
bool bfs(int rGraph[V][V], int s, int t, int parent[])
{
	// Create a visited array and mark all vertices as not visited 
	bool visited[V];
	memset(visited, 0, sizeof(visited));

	// Create a queue, enqueue source vertex and mark source vertex 
	// as visited 
	queue <int> q;
	q.push(s);
	visited[s] = true;
	parent[s] = -1;

	// Standard BFS Loop 
	while (!q.empty())
	{
		int u = q.front();
		q.pop();

		for (int v = 0; v < V; v++)
		{
			if (visited[v] == false && rGraph[u][v] > 0)
			{
				q.push(v);
				parent[v] = u;
				visited[v] = true;
			}
		}
	}

	// If we reached sink in BFS starting from source, then return 
	// true, else false 
	return (visited[t] == true);
}

// Returns the maximum flow from s to t in the given graph
int fordFulkerson(int graph[V][V], int s, int t)
{
	int u, v;

	// Create a residual graph and fill the residual graph with 
	// given capacities in the original graph as residual capacities 
	// in residual graph 
	int rGraph[V][V]; // Residual graph where rGraph[i][j] indicates  
					 // residual capacity of edge from i to j (if there 
					 // is an edge. If rGraph[i][j] is 0, then there is not)   
	for (u = 0; u < V; u++)
		for (v = 0; v < V; v++)
			rGraph[u][v] = graph[u][v];

	int parent[V];  // This array is filled by BFS and to store path 

	int max_flow = 0;  // There is no flow initially 

	// Augment the flow while tere is path from source to sink 
	while (bfs(rGraph, s, t, parent))
	{
		// Find minimum residual capacity of the edges along the 
		// path filled by BFS. Or we can say find the maximum flow 
		// through the path found. 
		int path_flow = INT_MAX;
		for (v = t; v != s; v = parent[v])
		{
			u = parent[v];
			path_flow = min(path_flow, rGraph[u][v]);
		}

		// update residual capacities of the edges and reverse edges 
		// along the path 
		for (v = t; v != s; v = parent[v])
		{
			u = parent[v];
			rGraph[u][v] -= path_flow;
			rGraph[v][u] += path_flow;
		}

		// Add path flow to overall flow 
		max_flow += path_flow;
	}

	// Return the overall flow 
	return max_flow;
}

// Driver program to test above functions 
int main()
{
	int graph[V][V] = {
		{0, 1, 0, 4, 0, 0},
		{0, 0, 2, 2, 3, 0},
		{0, 0, 0, 0, 0, 2},
		{0, 0, 3, 0, 0, 0},
		{0, 0, 0, 0, 0, 1},
		{0, 0, 0, 0, 0, 0}
	};

	cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);

	return 0;
}