#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>


#define INP_FILE in_file
#define OUT_FILE out_file
#ifndef DYNAMIC_PATHS_H
#define DYNAMIC_PATHS_H

// Biased Binary tree
typedef struct b_b_t {
    double netmin, netcost; // Not to be used when node is external.

    struct b_b_t *bparent;
    struct b_b_t *bhead, *btail; // External nodes point to themselves.
    struct b_b_t *bleft, *bright; // External nodes point to themselves.

    // These two have the right values only for nodes that are tails.
    struct b_b_t *dparent;
    double dcost; 


    int external;

    int reversed; // Not to be used when node is external.

    int value; // Equal to -1 for internal nodes.

    int wt, rank;
} BBTree_Node, *TDPath; 

typedef struct split_ret {
    TDPath p, q;
    double x, y;
} Split_ret, *TSplit_ret;

typedef struct destroy_ret {
    TDPath v, w;
    double x;
} Destroy_ret, *TDestroy_ret;

BBTree_Node* make_external_node(int value);

TDPath path(BBTree_Node *v);

BBTree_Node* head(TDPath p);

BBTree_Node* tail(TDPath p);

BBTree_Node* before(BBTree_Node *v);

BBTree_Node* after(BBTree_Node *v);

// Assumes v is not tail(path(v)).
double pcost(BBTree_Node *v);

// Assumes more than one node are contained in p.
BBTree_Node* pmincost(TDPath p);

void pupdate(TDPath p, double x);

void reverse(TDPath p);

// Assumes v and w are roots.
TDPath construct(TDPath v, TDPath w, double x);

// Assumes p is a root of a non-trivial tree.
TDestroy_ret destroy(TDPath u);

// Assumes v has an internal right child.
TDPath rotateleft(TDPath v);

// Assumes v has an internal left child.
TDPath rotateright(TDPath v);

TDPath concatenate(TDPath p, TDPath q, double x);

TSplit_ret split(TDPath v);

void free_path_without_leaves(TDPath p);

#endif
#ifndef DYNAMIC_TREES_H
#define DYNAMIC_TREES_H


typedef struct {
    BBTree_Node **vertices;

    int V;
} DTree, *TDTree;

TDTree init_trees(int V);

BBTree_Node* parent(BBTree_Node *v);

BBTree_Node* root(BBTree_Node *v);

double cost(BBTree_Node *v);

BBTree_Node* mincost(BBTree_Node *v);

void update(BBTree_Node *v, double x);

// Assumes v is a root.
void link(BBTree_Node *v, BBTree_Node *w, double x);

double cut(BBTree_Node *v);

void evert(BBTree_Node *v);

TDPath splice(TDPath p);

TDPath expose(BBTree_Node *v);

void free_dtree(TDTree tree);

#endif

int max(int a, int b) {
    return a > b ? a : b;
}

BBTree_Node* make_external_node(int value) 
{
    BBTree_Node *node = (BBTree_Node *) malloc(sizeof(*node));

    node->bparent = NULL;
    node->bleft = node->bright = node->btail = node->bhead = node;
    node->netcost = node->netmin = -1;
    node->external = 1;
    node->reversed = 0;
    node->value = value;
    node->wt = 1;
    node->dparent = NULL;
    node->rank = 0;
    node->dcost = 0;

    return node;
}


TDPath path(BBTree_Node *v) 
{
    while (v->bparent != NULL) {
        v = v->bparent;
    }

    return v;
}

int reversed(TDPath p) {    
    int reversed = 0;
    while (p != NULL) {
        reversed = reversed ^ p->reversed;
        p = p->bparent;
    }

    return reversed;
}

BBTree_Node* head(TDPath p)
{
    int reversal = reversed(p);
    if (reversal == 0) {
        return p->bhead;
    }

    return p->btail;
}

BBTree_Node* tail(TDPath p)
{
    int reversal = reversed(p);
    if (reversal == 0) {
        return p->btail;
    }

    return p->bhead;
}

BBTree_Node* before(BBTree_Node *v) 
{
    TDPath p = path(v);
    if (head(p) == v) {
        return NULL;
    }

    TDPath parent = v->bparent;
    int reversal = reversed(parent);

    while ((reversal == 0 && v == parent->bleft) || 
           (reversal == 1 && v == parent->bright)) {
        v = parent;
        parent = parent->bparent;
        reversal = reversal ^ parent->reversed;
    }

    if (reversal == 0) {
        parent = parent->bleft;
    } else {
        parent = parent->bright;
    }

    return parent->btail;
}

BBTree_Node* after(BBTree_Node *v)
{
    TDPath p = path(v);
    if (tail(p) == v) {
        return NULL;
    }

    TDPath parent = v->bparent;
    int reversal = reversed(parent);

    while ((reversal == 0 && v == parent->bright) || 
           (reversal == 1 && v == parent->bleft)) {
        v = parent;
        reversal = reversal ^ parent->reversed;
        parent = parent->bparent;
    }

    if (reversal == 0) {
        parent = parent->bright;
    } else {
        parent = parent->bleft;
    }

    return parent->bhead;
}

double grossmin(TDPath p) 
{
    double sum = p->netmin;
    TDPath parent = p->bparent;
    while (parent != NULL) {
        sum += parent->netmin;
        parent = parent->bparent;
    }

    return sum;
}

double grosscost(TDPath p) 
{
    return p->netcost + grossmin(p);
}

double pcost(BBTree_Node *v) 
{
    TDPath parent = v->bparent;
    int reversal = reversed(parent);

    while ((reversal == 0 && v == parent->bright) || 
           (reversal == 1 && v == parent->bleft)) {
        v = parent;
        parent = parent->bparent;
        reversal = reversal ^ parent->reversed;
    }

    return grosscost(parent);
}

BBTree_Node* pmincost(TDPath p)
{
    int reversal = reversed(p);
    while (1) {
        TDPath next = reversal == 0 ? p->bright : p->bleft;
        TDPath prev = reversal == 0 ? p->bleft : p->bright;
        if (next->external != 1) {
            if (next->netmin == 0) {
                p = next;
                reversal ^= p->reversed;
                continue;
            }
        }

        if (p->netcost == 0) {
            p = prev;
            return tail(p);
        }

        p = prev;
        reversal ^= p->reversed;
    }
}

void pupdate(TDPath p, double x) 
{
    p->netmin += x;

    return;
}

void reverse(TDPath p)
{
    p->reversed ^= 1;

    return;
}

void construct_set_vals(TDPath path, double x, TDPath v, TDPath w) {
    if (v->external == 1) {
        if (w->external == 1) {
            path->netmin = x;
            path->netcost = 0;
        } else {
            path->netmin = x < w->netmin ? x : w->netmin;
            path->netcost = x - path->netmin;
            w->netmin -= path->netmin;
        }
    } else {
        if (w->external == 1) {
            path->netmin = x < v->netmin ? x : v->netmin;
            path->netcost = x - path->netmin;
            v->netmin -= path->netmin;
        } else {
            path->netmin = v->netmin < w->netmin ? v->netmin : w->netmin;
            if (path->netmin > x) {
                path->netmin = x;
            }
            v->netmin -= path->netmin;
            w->netmin -= path->netmin;
            path->netcost = x - path->netmin;            
        }
    }
}

TDPath construct(TDPath v, TDPath w, double x) 
{
    TDPath path = (TDPath) malloc(sizeof(*path));

    path->bparent = NULL;
    path->bleft = v;
    path->bright = w;

    construct_set_vals(path, x, v, w);

    path->bhead = head(v);
    path->btail = tail(w);
    
    path->external = 0;
    path->reversed = 0;

    v->bparent = w->bparent = path;

    path->wt = v->wt + w->wt;

    path->value = -1;

    return path;
}

TDestroy_ret destroy(TDPath p) 
{
    TDestroy_ret ret_value = (TDestroy_ret) malloc(sizeof(*ret_value));
    
    int reversal = p->reversed;

    ret_value->v = reversal == 0 ? p->bleft : p->bright;
    ret_value->w = reversal == 0 ? p->bright : p->bleft;
    ret_value->x = p->netmin + p->netcost;
    ret_value->v->netmin += p->netmin;
    ret_value->w->netmin += p->netmin;

    free(p);

    ret_value->v->bparent = ret_value->w->bparent = NULL;

    ret_value->v->reversed ^= reversal;
    ret_value->w->reversed ^= reversal;


    return ret_value;
}

TDPath rotateleft(TDPath v) 
{
    TDPath w = v->bright;
    int rev_v = v->reversed;
    int rev_w = rev_v ^ w->reversed;

    double gc_v = v->netmin + v->netcost;

    if ((rev_v && rev_w) || (!rev_v && !rev_w)) {
        v->bright = w->bleft;
        w->bleft->bparent = v;
        w->bleft = v;
        w->bparent = v->bparent;
        v->bparent = w;
    } else {
        v->bright = w->bright;
        w->bright->bparent = v;

        w->bright = w->bleft;
       
        w->bparent = v->bparent;
        v->bparent = w;
        w->bleft = v;
    }

    w->bright->netmin += w->netmin;
    v->bright->netmin += w->netmin;

    double min_in_c = v->netmin + w->netmin + v->bright->netmin;
    double min_in_x = v->netmin + v->bleft->netmin;
    double min;

    if (v->bright->external == 0 && v->bleft->external == 0) {
        min = min_in_c < min_in_x ? min_in_c : min_in_x;
    } else if (v->bright->external == 0) {
        min = min_in_c;
    } else if (v->bleft->external == 0) {
        min = min_in_x;
    } else {
        min = gc_v;
    }
    min = min < gc_v ? min : gc_v;

    w->netcost += w->netmin;
    w->netmin = v->netmin;
    v->netmin = min - w->netmin;
    v->netcost = v->netcost + w->netmin - min;

    v->bleft->netmin -= v->netmin;
    v->bright->netmin -= v->netmin;

    w->bright->reversed = w->bright->reversed ^ w->reversed;
    v->bright->reversed = v->bright->reversed ^ w->reversed;

    v->reversed = 0;
    w->reversed = rev_v;

    rev_w = rev_v;

    if (rev_v == 1) {
        v->btail = head(v->bright);
        v->bhead = tail(v->bleft);

        w->btail = head(w->bright);
        w->bhead = tail(w->bleft);
    } else {
        v->btail = tail(v->bright);
        v->bhead = head(v->bleft);

        w->btail = tail(w->bright);
        w->bhead = head(w->bleft);
    }


    w->wt = v->wt;
    v->wt = v->wt - w->bright->wt;

    return w;
}

TDPath rotateright(TDPath v) 
{
    TDPath w = v->bleft;
    int rev_v = v->reversed;
    int rev_w = rev_v ^ w->reversed;

    double gc_v = v->netmin + v->netcost;

    if ((rev_v && rev_w) || (!rev_v && !rev_w)) {
        v->bleft = w->bright;
        w->bright->bparent = v;
        w->bright = v;
        w->bparent = v->bparent;
        v->bparent = w;
    } else {
        v->bleft = w->bleft;
        w->bleft->bparent = v;

        w->bleft = w->bright;
       
        w->bparent = v->bparent;
        v->bparent = w;
        w->bright = v;
    }

    w->bleft->netmin += w->netmin;
    v->bleft->netmin += w->netmin;

    double min_in_c = v->netmin + w->netmin + v->bleft->netmin;
    double min_in_x = v->netmin + v->bright->netmin;
    double min;

    if (v->bleft->external == 0 && v->bright->external == 0) {
        min = min_in_c < min_in_x ? min_in_c : min_in_x;
    } else if (v->bleft->external == 0) {
        min = min_in_c;
    } else if (v->bright->external == 0) {
        min = min_in_x;
    } else {
        min = gc_v;
    }
    min = min < gc_v ? min : gc_v;

    w->netcost += w->netmin;
    w->netmin = v->netmin;
    v->netmin = min - w->netmin;
    v->netcost = v->netcost + w->netmin - min;

    v->bright->netmin -= v->netmin;
    v->bleft->netmin -= v->netmin;

    w->bleft->reversed = w->bleft->reversed ^ w->reversed;
    v->bleft->reversed = v->bleft->reversed ^ w->reversed;

    v->reversed = 0;
    w->reversed = rev_v;

    rev_w = rev_v;

    if (rev_v == 1) {
        v->btail = head(v->bright);
        v->bhead = tail(v->bleft);

        w->btail = head(w->bright);
        w->bhead = tail(w->bleft);
    } else {
        v->btail = tail(v->bright);
        v->bhead = head(v->bleft);

        w->btail = tail(w->bright);
        w->bhead = head(w->bleft);
    }

    w->wt = v->wt;
    v->wt = v->wt - w->bleft->wt;
    return w;
}

TDPath tiltleft(TDPath p) 
{
    if (p->external == 0) {
        if (p->bleft->external == 0 && p->bright->external == 0) {
            if (p->rank == p->bleft->rank && p->rank == p->bright->rank) {
                p->rank++;
                return p;
            }
        }
        if (p->bright->external == 0) {
            if (p->rank == p->bright->rank) {
                p = rotateleft(p);
                return p;
            }
        }
    }

    return p;
}

TDPath tiltright(TDPath p) 
{
    if (p->external == 0) {
        if (p->bright->external == 0 && p->bleft->external == 0) {
            if (p->rank == p->bright->rank && p->rank == p->bleft->rank) {
                p->rank++;
                return p;
            }
        }
        if (p->bleft->external == 0) {
            if (p->rank == p->bleft->rank) {
                p = rotateright(p);
                return p;
            }
        }
    }

    return p;
}

TDPath concatenate(TDPath p, TDPath q, double x)
{
    if (p->external == 1) {
        p->rank = floor(log2(p->wt));
    }
    if (q->external == 1) {
        p->rank = floor(log2(p->wt));
    }
    
    if ((p->rank == q->rank) || (p->rank > q->rank && 
    p->external == 1) || (p->rank < q->rank && q->external == 1)) {
        TDPath res = construct(p, q, x);
        res->rank = 1 + max(p->rank, q->rank);
        return res;
    }

    if (p->reversed == 1) {
        p->reversed ^= 1;
        TDPath aux = p->bhead;
        p->bhead = p->btail;
        p->btail = aux;
        p->bleft->reversed ^= 1;
        p->bright->reversed ^= 1;
        aux = p->bleft;
        p->bleft = p->bright;
        p->bright = aux;
    }

    if (q->reversed == 1) {
        q->reversed ^= 1;
        TDPath aux = q->bhead;
        q->bhead = q->btail;
        q->btail = aux;
        q->bleft->reversed ^= 1;
        q->bright->reversed ^= 1;
        aux = q->bleft;
        q->bleft = q->bright;
        q->bright = aux;
    }

    
    if (p->rank > q->rank) {
        p = tiltleft(p);
        p->wt += q->wt;
        p->btail = q->btail;

        double min_cost = p->netmin < x ? p->netmin : x;
        if (q->external == 0 && q->netmin < min_cost) {
            min_cost = q->netmin;
        }

        double diff = p->netmin - min_cost;

        p->bleft->netmin += diff;

        p->bright->netmin += p->netmin;

        p->netmin = min_cost;

        p->netcost += diff;

        p->bright = concatenate(p->bright, q, x);

        p->bright->bparent = p;

        p->bright->netmin -= p->netmin;

        return p;
    } else {
        q = tiltright(q);
        q->wt += p->wt;
        q->bhead = p->bhead;

        double min_cost = q->netmin < x ? q->netmin : x;
        if (p->external == 0 && p->netmin < min_cost) {
            min_cost = p->netmin;
        }

        double diff = q->netmin - min_cost;

        q->bright->netmin += diff;

        q->bleft->netmin += q->netmin;

        q->netmin = min_cost;

        q->netcost += diff;

        q->bleft = concatenate(p, q->bleft, x);

        q->bleft->bparent = q;

        q->bleft->netmin -= q->netmin;

        return q;
    }
}

TSplit_ret split(BBTree_Node *x)
{
    TSplit_ret res = (TSplit_ret) malloc(sizeof(*res));
    res->p = NULL;
    res->q = NULL;
    TDPath p = path(x);

    if (tail(p) != x) {
        res->y = pcost(x);
    }
    if (head(p) != x) {
        res->x = pcost(before(x));
    }
    if (head(p) == x && tail(p) == x) {
        return res;
    }

    int reversal;
    TDPath v = x;
    TDPath pv = v->bparent;
    if (pv != NULL) {
        reversal = reversed(pv);
    }
    double min_now = grossmin(pv);
    while (pv != NULL) {
        if ((reversal == 0 && pv->bright == v) ||
        (reversal == 1 && pv->bleft == v)) {
            TDPath real_left;
            if (reversal == 0) {
                real_left = pv->bleft;
            } else {
                real_left = pv->bright;
            }
            real_left->netmin += min_now;
            real_left->reversed ^= reversal;
            if (res->p == NULL) {
                res->p = real_left;
            } else {
                res->p = concatenate(real_left, res->p, min_now + pv->netcost);
            }
        } else {
            TDPath real_right;
            if (reversal == 0) {
                real_right = pv->bright;
            } else {
                real_right = pv->bleft;
            }
            real_right->netmin += min_now;
            real_right->reversed ^= reversal;
            if (res->q == NULL) {
                res->q = real_right;
            } else {
                res->q = concatenate(res->q, real_right, min_now + pv->netcost);
            }
        }
        reversal ^= pv->reversed;
        min_now -= pv->netmin;
        if (v->external != 1) {
            free(v);
        }
        if (res->p != NULL) {
            res->p->bparent = NULL;
        }
        if (res->q != NULL) {
            res->q->bparent = NULL;
        }
        v = pv;
        pv = pv->bparent;
    }

    free(v);
    
    x->bparent = NULL;

    return res;
}

void free_path_without_leaves(TDPath p)
{
    if (p->external == 1) {
        p->bparent = NULL;
        return;
    }
    free_path_without_leaves(p->bleft);
    free_path_without_leaves(p->bright);
    free(p);

    return;
}


TDTree init_trees(int V)
{
    TDTree forest = (TDTree) malloc(sizeof(*forest));
    forest->V = V;
    forest->vertices = (TDPath*) malloc(V * sizeof(TDPath));
    for (int i = 0; i < V; i++) {
        forest->vertices[i] = make_external_node(i);
    }

    return forest;
}

TDPath splice(TDPath p)
{
    TDPath v, q, r;
    double x, y;
    v = tail(p)->dparent;
    if (v == NULL) {
        return p;
    }
    TSplit_ret split_list = split(v);
    q = split_list->p;
    r = split_list->q;
    x = split_list->x;
    y = split_list->y;
    free(split_list);
    v->wt -= p->wt;
    if (q != NULL) {
        tail(q)->dparent = v;
        tail(q)->dcost = x;
        v->wt += q->wt;
    }

    p = concatenate(p, path(v), tail(p)->dcost);
    if (r != NULL) {
        concatenate(p, r, y);
    }

    return p;
}

TDPath expose(BBTree_Node *v)
{
    TDPath p, q, r;
    double x, y;
    TSplit_ret spl_ret = split(v);
    q = spl_ret->p;
    r = spl_ret->q;
    x = spl_ret->x;
    y = spl_ret->y;
    free(spl_ret);
    if (q != NULL) {
        tail(q)->dparent = v;
        tail(q)->dcost = x;
        v->wt += q->wt;
    }
    if (r != NULL) {
        p = concatenate(path(v), r, y);
    } else {
        p = path(v);
    }

    while (tail(p)->dparent != NULL) {
        p = splice(p);
    }

    return p;
}

BBTree_Node* parent(BBTree_Node *v)
{
    if (v == tail(path(v))) {
        return v->dparent;
    } else {
        return after(v);
    }
}

BBTree_Node* root(BBTree_Node *v)
{
    return tail(expose(v));
}

double cost(BBTree_Node *v)
{
    if (v == tail(path(v))) {
        return v->dcost;
    } 

    return pcost(v);
}

BBTree_Node* mincost(BBTree_Node *v)
{
    return pmincost(expose(v));
}

void update(BBTree_Node *v, double x)
{
    pupdate(expose(v), x);

    return;
}

void link(BBTree_Node *v, BBTree_Node *w, double x)
{
    concatenate(path(v), expose(w), x);

    return;
}

double cut(BBTree_Node *v)
{
    expose(v);
    TSplit_ret sp_ret = split(v);
    double y = sp_ret->y;
    free(sp_ret);
    v->dparent = NULL;

    return y;
}

void evert(BBTree_Node *v)
{
    reverse(expose(v));
    v->dparent = NULL;

    return;
}

void free_dtree(TDTree tree)
{
    for (int i = 0; i < tree->V; i++) {
        free_path_without_leaves(path(tree->vertices[i]));
        free(tree->vertices[i]);
    }
    free(tree->vertices);
    free(tree);

    return;
}




typedef struct queue_cell {
    int value;
    struct queue_cell *next;
} QCell, *TQCell;

typedef struct squeue {
    TQCell head;
    TQCell tail;
} Queue, *TQueue;

void enqueue(TQueue queue, int val)
{
    TQCell cell = (TQCell) malloc(sizeof(*cell));
    cell->value = val;
    cell->next = NULL;
    if (queue->head == NULL) {
        queue->head = cell;
        queue->tail = cell;

        return;
    }

    queue->tail->next = cell;
    queue->tail = cell;

    return;
}

int dequeue(TQueue queue)
{
    int value = queue->head->value;

    if (queue->head == queue->tail) {
        free(queue->head);
        queue->head = queue->tail = NULL;

        return value;
    }

    TQCell aux = queue->head;
    queue->head = queue->head->next;
    free(aux);

    return value;
}

void destroy_queue(TQueue queue)
{
    while (queue->head != NULL) {
        dequeue(queue);
    }
    free(queue);

    return;
}

typedef struct dgraph_edge {
    int id;
    double cost;
    double flow;
    struct dgraph_edge *next;
} DGEdge, *TDGEdge;

typedef struct dgraph {
    int V, E;
    TDGEdge *out_edges;
    TDGEdge *in_edges;
} DGraph, *TDGraph;

void make_and_add_edges(TDGraph graph, int v1, int v2, double cost)
{
    TDGEdge edge_out = (TDGEdge) calloc(1, sizeof(*edge_out));

    edge_out->id = v2;
    edge_out->cost = cost;
    edge_out->flow = 0;

    edge_out->next = graph->out_edges[v1];
    graph->out_edges[v1] = edge_out;

    return;
}

void make_res_graph_edges(TDGraph graph, TDGraph res_graph)
{
    for (int i = 0; i < graph->V; i++) {
        TDGEdge iter = graph->out_edges[i];
        while (iter != NULL) {
            make_and_add_edges(res_graph, i, iter->id, iter->cost - iter->flow);
            make_and_add_edges(res_graph, iter->id, i, iter->flow);

            iter = iter->next;
        }
    }

    return;
}

int make_level_graph_edges(TDGraph res_graph, TDGraph level_graph)
{
    int V = res_graph->V;
    int *levels = (int *) calloc(V, sizeof(int));
    int *visited = (int *) calloc(V, sizeof(int));

    TQueue queue = (TQueue) malloc(sizeof(*queue));
    queue->head = queue->tail = NULL;

    enqueue(queue, 0);

    int current_vertex;

    while (queue->head != NULL) {
        current_vertex = dequeue(queue);
        TDGEdge iter = res_graph->out_edges[current_vertex];
        while (iter != NULL) {
            if ((levels[iter->id] != 0 && iter->id != V - 1 && levels[iter->id] <= levels[current_vertex]) ||
                    iter->cost <= 1e-9 || iter->id == 0) {
                iter = iter->next;
                continue;
            }

            make_and_add_edges(level_graph, current_vertex, iter->id, iter->cost);
            TDGEdge edge_in = (TDGEdge) calloc(1, sizeof(*edge_in));

            edge_in->id = current_vertex;
            edge_in->cost = iter->cost;
            edge_in->flow = 0;

            edge_in->next = level_graph->in_edges[iter->id];
            level_graph->in_edges[iter->id] = edge_in;
            
            levels[iter->id] = levels[current_vertex] + 1;
            if (visited[iter->id] == 0) {
                enqueue(queue, iter->id);
            }
            visited[iter->id] = 1;

            iter = iter->next;
        }
    }

    if (levels[V - 1] == 0) {
        return 0;
    }

    return 1;
}

void remove_out_edge_graph(TDGraph graph, int v1, int v2)
{
    TDGEdge iter = graph->out_edges[v1];
    TDGEdge parent = NULL;
    while (iter != NULL) {
        if (iter->id == v2) {
            if (parent == NULL) {
                graph->out_edges[v1] = iter->next;
            } else {
                parent->next = iter->next;
            }
            free(iter);

            return;
        }

        parent = iter;
        iter = iter->next;
    }

    return;
}

void remove_in_edge_graph(TDGraph graph, int v1, int v2)
{
    TDGEdge iter = graph->in_edges[v2];
    TDGEdge parent = NULL;
    while (iter != NULL) {
        if (iter->id == v2) {
            if (parent == NULL) {
                graph->in_edges[v2] = iter->next;
            } else {
                parent->next = iter->next;
            }
            free(iter);

            return;
        }

        parent = iter;
        iter = iter->next;
    }

    return;
}

void update_flow(TDGraph graph, int v1, int v2, double flow)
{
    TDGEdge iter = graph->out_edges[v1];
    while (iter != NULL) {
        if (iter->id == v2) {
            iter->flow += flow;
            return;
        }

        iter = iter->next;
    }

    iter = graph->out_edges[v2];

    while (iter != NULL) {
        if (iter->id == v1) {
            iter->flow -= flow;
            return;
        }

        iter = iter->next;
    }

    return;
}

void update_cost_level_graph(TDGraph graph, int v1, int v2, double cost)
{
    TDGEdge iter = graph->out_edges[v1];
    while (iter != NULL) {
        if (iter->id == v2) {
            iter->cost -= cost;
            return;
        }

        iter = iter->next;
    }

    return;
}

void update_res(TDGraph res_graph, int v1, int v2, double flow)
{
    TDGEdge iter = res_graph->out_edges[v1];
    while (iter != NULL) {
        if (iter->id == v2) {
            iter->cost -= flow;
            break;
        }

        iter = iter->next;
    }

    iter = res_graph->out_edges[v2];

    while (iter != NULL) {
        if (iter->id == v1) {
            iter->cost += flow;
            return;
        }

        iter = iter->next;
    }
}

void update_both(TDGraph graph, TDGraph res_graph, int v1, int v2, double res_cap)
{
    TDGEdge iter = graph->out_edges[v1];
    double capacity;
    while (iter != NULL) {
        if (iter->id == v2) {
            capacity = iter->cost;
            iter->flow = iter->cost - res_cap;
        }

        iter = iter->next;
    }
    iter = graph->out_edges[v2];
    while (iter != NULL) {
        if (iter->id == v1) {
            capacity = iter->cost;
            iter->flow = res_cap;
        }

        iter = iter->next;
    }

    iter = res_graph->out_edges[v1];
    while (iter != NULL) {
        if (iter->id == v2) {
            iter->cost = res_cap;
        }

        iter = iter->next;
    }
    iter = res_graph->out_edges[v2];
    while (iter != NULL) {
        if (iter->id == v1) {
            iter->cost = capacity - res_cap;
        }

        iter = iter->next;
    }

    return;
}

void dfs_until_bf_and_modify_graphs(TDGraph graph, TDGraph res_graph, TDGraph level_graph, TDTree forest)
{
    int V = level_graph->V;
    while (1) {
        BBTree_Node *v = root(forest->vertices[0]);
        if (v->value == V - 1) {
            v = mincost(forest->vertices[0]);
            double c = cost(v);
            update(forest->vertices[0], -c);
            while (cost(v) == 0) {
                BBTree_Node *w = parent(v);
                update_both(graph, res_graph, v->value, w->value, cost(v));
                remove_out_edge_graph(level_graph, v->value, w->value);
                remove_in_edge_graph(level_graph, v->value, w->value);

                cut(v);

                if (parent(forest->vertices[0]) == NULL) {
                    break;
                }
                v = mincost(forest->vertices[0]);
            }
        } else {
            if (level_graph->out_edges[v->value] == NULL) {
                if (v == forest->vertices[0]) {
                    for (int i = 1; i < V; i++) {
                        BBTree_Node *aux = forest->vertices[i];
                        BBTree_Node *w = parent(aux);
                        if (w != NULL) {
                            update_both(graph, res_graph, aux->value, w->value, cost(aux));
                            remove_out_edge_graph(level_graph, v->value, w->value);
                            remove_in_edge_graph(level_graph, v->value, w->value);
                        }
                    }
                    return;
                } else {
                    TDGEdge iter = level_graph->in_edges[v->value];
                    while (iter != NULL) {
                        double c;
                        TDGEdge aux = iter->next;
                        remove_out_edge_graph(level_graph, iter->id, v->value);
                        BBTree_Node *w = parent(forest->vertices[iter->id]);
                        if (w == v) {
                            c = cost(forest->vertices[iter->id]);
                            update_both(graph, res_graph, iter->id, v->value, c);
                            cut(forest->vertices[iter->id]);
                        }

                        remove_in_edge_graph(level_graph, iter->id, v->value);
                        iter = aux;
                    }
                }
            } else {
                link(v, forest->vertices[level_graph->out_edges[v->value]->id], level_graph->out_edges[v->value]->cost);
            }
        }
    }
}

void free_graph(TDGraph graph)
{
    int V = graph->V;
    for (int i = 0; i < V; i++) {
        TDGEdge iter = graph->out_edges[i];
        TDGEdge aux;
        while (iter != NULL) {
            aux = iter->next;
            free(iter);
            iter = aux;
        }
        while (iter != NULL) {
            aux = iter->next;
            free(iter);
            iter = aux;
        }
    }
    free(graph->out_edges);
    free(graph->in_edges);
    free(graph);

    return;
}

void free_edges(TDGraph level_graph)
{
    int V = level_graph->V;
    for (int i = 0; i < V; i++) {
        TDGEdge iter = level_graph->out_edges[i];
        TDGEdge aux;
        while (iter != NULL) {
            aux = iter->next;
            free(iter);
            iter = aux;
        }
        iter = level_graph->in_edges[i];
        while (iter != NULL) {
            aux = iter->next;
            free(iter);
            iter = aux;
        }
    }
    for (int i = 0; i < V; i++) {
        level_graph->out_edges[i] = NULL;
        level_graph->in_edges[i] = NULL;
    }

    return;
}

double dinic_max_flow(TDGraph graph)
{
    TDGraph res_graph = (TDGraph) malloc(sizeof(*res_graph));
    res_graph->V = graph->V;
    res_graph->E = 2 * graph->E;
    res_graph->out_edges = (TDGEdge *) calloc(res_graph->V, sizeof(TDGEdge));
   
    make_res_graph_edges(graph, res_graph);

    TDGraph level_graph = (TDGraph) malloc(sizeof(*level_graph));
    level_graph->V = graph->V;
    level_graph->out_edges = (TDGEdge *) calloc(res_graph->V, sizeof(TDGEdge));
    level_graph->in_edges = (TDGEdge *) calloc(res_graph->V, sizeof(TDGEdge));
    level_graph->E = 0;

    TDTree forest = init_trees(graph->V);

    int there_is_path = make_level_graph_edges(res_graph, level_graph);
    while (there_is_path == 1) {
        dfs_until_bf_and_modify_graphs(graph, res_graph, level_graph, forest);
        for (int i = 0; i < graph->V; i++) {
            free_path_without_leaves(forest->vertices[i]);
            forest->vertices[i]->dparent = NULL;
            forest->vertices[i]->wt = 1;
            forest->vertices[i]->rank = 0;
        }
        
        free_edges(level_graph);
        there_is_path = make_level_graph_edges(res_graph, level_graph);
    }

    double flow = 0;
    TDGEdge iter = graph->out_edges[0];
    while (iter != NULL) {
        flow += iter->flow;
        iter = iter->next;
    }

    free_graph(res_graph);

    return flow;
}

int main( int argc, const char* args[] )
{
    TDGraph graph = (TDGraph) malloc(sizeof(*graph));

    FILE *in_file = fopen("maxflow.in", "r");
    FILE *out_file = fopen("maxflow.out", "w");
    
    fscanf(INP_FILE, "%d%d", &graph->V, &graph->E);
    graph->out_edges = (TDGEdge *) calloc(graph->V, sizeof(TDGEdge));

    int v1, v2;
    double cost;
    for (int i = 0; i < graph->E; i++) {
        fscanf(INP_FILE, "%d%d%lf", &v1, &v2, &cost);
        v1--;
        v2--;
        if (v2 == 0 || v1 == graph->V - 1) {
            printf("Vertex giving to source or taking from sink.\n");
            return 1;
        }
        make_and_add_edges(graph, v1, v2, cost);
    }
    double max_flow = dinic_max_flow(graph);
    fprintf(OUT_FILE, "%d\n", (int)max_flow);
    free_graph(graph);

    return 0;
}