#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int INF = (unsigned)-1 >> 1;
const int SOURCE = 0;
const int SINK = 1;

int T, N;

struct Dinic {
    struct Edge {
        // deistination, reverse index, residual capacity
        int dest, rev, res;
        Edge(int _dest, int _rev, int _res) 
            : dest(_dest), rev(_rev), res(_res) {

        }
    };

    int _size;
    vector < vector < Edge > > _graph;
    vector < int > dist;

    Dinic(int size) {
        _size = size;
        _graph.resize(_size);
    }

    void addEdge(int here, int there, int capacity) {
        Edge forward = Edge(there, _graph[there].size(), capacity);
        Edge reverse = Edge(here, _graph[here].size(), 0);
        _graph[here].push_back(forward);
        _graph[there].push_back(reverse);
    }

    // assign levels to vertices by BFS
    // return 1 if sink is reachable
    int bfs(int source, int sink) {
        dist = vector < int > (_size, -1);
        queue < int > q;

        dist[source] = 0;
        q.push(source);

        while (!q.empty()) {
            int here = q.front(); q.pop();
            for (auto edge : _graph[here]) {
                if (edge.res > 0 && dist[edge.dest] == -1) {
                    dist[edge.dest] = dist[here] + 1;
                    q.push(edge.dest);
                }
            }
        }

        return dist[sink] != -1;
    }

    // find augmenting path by DFS
    int dfs(int here, int sink, int flow) {
        if (here == sink) {
            return flow;
        }

        for (auto &edge : _graph[here]) {
            if (dist[edge.dest] > dist[here] && edge.res > 0) {
                int bottleneck = dfs(edge.dest, sink, min(flow, edge.res));
                if (bottleneck > 0) {
                    edge.res -= bottleneck;
                    _graph[edge.dest][edge.rev].res += bottleneck;
                    return bottleneck;
                }
            }
        }
        return 0;
    }

    int maxFlow(int source, int sink) {
        int ret = 0;
        // while sink is reachable
        while (bfs(source, sink)) {
            // increase by blocking flow
            while (int delta = dfs(source, sink, INF)) {
                ret += delta;
            }
        }
        return ret;
    }
};