stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include "bits/stdc++.h"

#define ll long long

#define lld long double

#define MOD 1000000007

#define inf 1000000000000000000ll

#define pii pair<int,int>

#define f first

#define s second

#define pb push_back

#define mp make_pair

#define all(v) v.begin(),v.end()

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

ll power(ll x,ll y, ll md=inf){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}

 

using namespace std;





#define endl '\n'

#define int ll



signed main() {

	fast;



	int h,w;

	cin>>h>>w;



	pii v[200002];

	for(int i=0;i<h;i++) cin>>v[i].f>>v[i].s;



	map<int,int> mp;

	for(int i=1;i<=w;i++) mp[i] = 0;



	map<int, int> mini = {{0,w}};



	for(int i=0;i<h;i++) {

		int l = v[i].f;

		int r = v[i].s;



		auto it = mp.lower_bound(l);

		int mn = inf;



		while(it!=mp.end() && it->f <= r) {

			mn = min(mn, r+1-(it->f)+(it->s));

			auto it1 = it++;

			mini[it1->s]--;

			if(mini[it1->s]==0) mini.erase(it1->s);

			mp.erase(it1);

		}



		if(r+1<=w && mn<inf) {

			if(mp.count(r+1) && mp[r+1] > mn) {

				mini[mp[r+1]]--;

				if(mini[mp[r+1]]==0) mini.erase(mp[r+1]);

				mini[mn]++;

				mp[r+1] = mn;

			}

			else if(!mp.count(r+1)){

				mp[r+1] = mn;

				mini[mn]++;

			}

		}



		if(mini.size()) cout<<mini.begin()->f+i+1<<endl;

		else cout<<-1<<endl;



	}

}

// Faster C++ solution for the same problem (measured speedup: 1.6166037399805988x):
#include "bits/stdc++.h"

#define ll long long

#define lld long double

#define MOD 1000000007

#define inf 1000000007

#define pii pair<int,int>

#define f first

#define s second

#define pb push_back

#define mp make_pair

#define all(v) v.begin(),v.end()

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

ll power(ll x,ll y, ll md=inf){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}

 

using namespace std;





#define endl '\n'

// #define int ll



signed main() {

	fast;



	int h,w;

	cin>>h>>w;



	pii v[200002];

	for(int i=0;i<h;i++) cin>>v[i].f>>v[i].s;



	map<int,int> mp;

	for(int i=1;i<=w;i++) mp[i] = 0;



	map<int,int> mini = {{0,w}};



	for(int i=0;i<h;i++) {

		int r = v[i].s;



		auto it = mp.lower_bound(v[i].f);





		if(r==w) {

			while(it!=mp.end() && it->f <= r) {

				auto it1 = it++;

				auto it2 = mini.find(it1->s);

				if(it2->s==1) mini.erase(it2);

				else it2->s --;

				mp.erase(it1);

			}

		}

		else {

			int mn = inf;



			while(it!=mp.end() && it->f <= r) {

				mn = min(mn, r+1-(it->f)+(it->s));

				auto it1 = it++;

				auto it2 = mini.find(it1->s);

				if(it2->s==1) mini.erase(it2);

				else it2->s --;

				mp.erase(it1);

			}



			if(mn<inf) {

				if(it!=mp.end() && it->f == r + 1) {

					if(it->s > mn) {

						auto it1 = mini.find(it->s);

						if(it1->s ==1) mini.erase(it1);

						else it1->s --;

						mini[mn]++;

						it->s = mn;

					}

				}

				else {

					mp.insert({r+1,mn});

					mini[mn]++;

				}

			}

		}



		if(mini.size()) cout<<mini.begin()->f+i+1<<endl;

		else cout<<-1<<endl;



	}

}
// Slower C++ solution:
#include "bits/stdc++.h"

#define ll long long

#define lld long double

#define MOD 1000000007

#define inf 1000000000000000000ll

#define pii pair<int,int>

#define f first

#define s second

#define pb push_back

#define mp make_pair

#define all(v) v.begin(),v.end()

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

ll power(ll x,ll y, ll md=inf){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}

 

using namespace std;





#define endl '\n'

#define int ll



signed main() {

	fast;



	int h,w;

	cin>>h>>w;



	pii v[200002];

	for(int i=0;i<h;i++) cin>>v[i].f>>v[i].s;



	map<int,int> mp;

	for(int i=1;i<=w;i++) mp[i] = 0;



	map<int,int> mini = {{0,w}};



	for(int i=0;i<h;i++) {

		int l = v[i].f;

		int r = v[i].s;



		auto it = mp.lower_bound(l);

		int mn = inf;



		while(it!=mp.end() && it->f <= r) {

			mn = min(mn, r+1-(it->f)+(it->s));

			auto it1 = it++;

			mini[it1->s]--;

			if(mini[it1->s]==0) mini.erase(it1->s);

			mp.erase(it1);

		}



		if(r+1<=w && mn<inf) {

			if(it!=mp.end() && it->f == r + 1) {

				if(it->s > mn) {

					mini[it->s]--;

					if(mini[it->s]==0) mini.erase(it->s);

					mini[mn]++;

					mp[r+1] = mn;

				}

			}

			else {

				mp[r+1] = mn;

				mini[mn]++;

			}

		}



		if(mini.size()) cout<<mini.begin()->f+i+1<<endl;

		else cout<<-1<<endl;



	}

}

// Faster C++ solution for the same problem (measured speedup: 1.6164559978867232x):
#include "bits/stdc++.h"

#define ll long long

#define lld long double

#define MOD 1000000007

#define inf 1000000007

#define pii pair<int,int>

#define f first

#define s second

#define pb push_back

#define mp make_pair

#define all(v) v.begin(),v.end()

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

ll power(ll x,ll y, ll md=inf){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}

 

using namespace std;





#define endl '\n'

// #define int ll



signed main() {

	fast;



	int h,w;

	cin>>h>>w;



	pii v[200002];

	for(int i=0;i<h;i++) cin>>v[i].f>>v[i].s;



	map<int,int> mp;

	for(int i=1;i<=w;i++) mp[i] = 0;



	map<int,int> mini = {{0,w}};



	for(int i=0;i<h;i++) {

		int r = v[i].s;



		auto it = mp.lower_bound(v[i].f);





		if(r==w) {

			while(it!=mp.end() && it->f <= r) {

				auto it1 = it++;

				auto it2 = mini.find(it1->s);

				if(it2->s==1) mini.erase(it2);

				else it2->s --;

				mp.erase(it1);

			}

		}

		else {

			int mn = inf;



			while(it!=mp.end() && it->f <= r) {

				mn = min(mn, r+1-(it->f)+(it->s));

				auto it1 = it++;

				auto it2 = mini.find(it1->s);

				if(it2->s==1) mini.erase(it2);

				else it2->s --;

				mp.erase(it1);

			}



			if(mn<inf) {

				if(it!=mp.end() && it->f == r + 1) {

					if(it->s > mn) {

						auto it1 = mini.find(it->s);

						if(it1->s ==1) mini.erase(it1);

						else it1->s --;

						mini[mn]++;

						it->s = mn;

					}

				}

				else {

					mp.insert({r+1,mn});

					mini[mn]++;

				}

			}

		}



		if(mini.size()) cout<<mini.begin()->f+i+1<<endl;

		else cout<<-1<<endl;



	}

}
// Slower C++ solution:
#include "bits/stdc++.h"

#define ll long long

#define lld long double

#define MOD 1000000007

#define inf 1000000000000000000ll

#define pii pair<int,int>

#define f first

#define s second

#define pb push_back

#define mp make_pair

#define all(v) v.begin(),v.end()

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

ll power(ll x,ll y, ll md=inf){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}

 

using namespace std;





#define endl '\n'

#define int ll



signed main() {

	fast;



	int h,w;

	cin>>h>>w;



	pii v[200002];

	for(int i=0;i<h;i++) cin>>v[i].f>>v[i].s;



	map<int,int> mp;

	for(int i=1;i<=w;i++) mp[i] = 0;



	map<int,int> mini = {{0,w}};



	for(int i=0;i<h;i++) {

		int l = v[i].f;

		int r = v[i].s;



		auto it = mp.lower_bound(l);

		int mn = inf;



		while(it!=mp.end() && it->f <= r) {

			mn = min(mn, r+1-(it->f)+(it->s));

			auto it1 = it++;

			mini[it1->s]--;

			if(mini[it1->s]==0) mini.erase(it1->s);

			mp.erase(it1);

		}



		if(r+1<=w && mn<inf) {

			if(it!=mp.end() && it->f == r + 1) {

				if(it->s > mn) {

					mini[it->s]--;

					if(mini[it->s]==0) mini.erase(it->s);

					mini[mn]++;

					it->s = mn;

				}

			}

			else {

				mp.insert({r+1,mn});

				mini[mn]++;

			}

		}



		if(mini.size()) cout<<mini.begin()->f+i+1<<endl;

		else cout<<-1<<endl;



	}

}

// Faster C++ solution for the same problem (measured speedup: 1.6162033158164697x):
#include "bits/stdc++.h"

#define ll long long

#define lld long double

#define MOD 1000000007

#define inf 1000000007

#define pii pair<int,int>

#define f first

#define s second

#define pb push_back

#define mp make_pair

#define all(v) v.begin(),v.end()

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

ll power(ll x,ll y, ll md=inf){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}

 

using namespace std;





#define endl '\n'

// #define int ll



signed main() {

	fast;



	int h,w;

	cin>>h>>w;



	pii v[200002];

	for(int i=0;i<h;i++) cin>>v[i].f>>v[i].s;



	map<int,int> mp;

	for(int i=1;i<=w;i++) mp[i] = 0;



	map<int,int> mini = {{0,w}};



	for(int i=0;i<h;i++) {

		int r = v[i].s;



		auto it = mp.lower_bound(v[i].f);





		if(r==w) {

			while(it!=mp.end() && it->f <= r) {

				auto it1 = it++;

				auto it2 = mini.find(it1->s);

				if(it2->s==1) mini.erase(it2);

				else it2->s --;

				mp.erase(it1);

			}

		}

		else {

			int mn = inf;



			while(it!=mp.end() && it->f <= r) {

				mn = min(mn, r+1-(it->f)+(it->s));

				auto it1 = it++;

				auto it2 = mini.find(it1->s);

				if(it2->s==1) mini.erase(it2);

				else it2->s --;

				mp.erase(it1);

			}



			if(mn<inf) {

				if(it!=mp.end() && it->f == r + 1) {

					if(it->s > mn) {

						auto it1 = mini.find(it->s);

						if(it1->s ==1) mini.erase(it1);

						else it1->s --;

						mini[mn]++;

						it->s = mn;

					}

				}

				else {

					mp.insert({r+1,mn});

					mini[mn]++;

				}

			}

		}



		if(mini.size()) cout<<mini.begin()->f+i+1<<endl;

		else cout<<-1<<endl;



	}

}
// Slower C++ solution:
#include "bits/stdc++.h"

#define ll long long

#define lld long double

#define MOD 1000000007

#define inf 1000000000000000000ll

#define pii pair<int,int>

#define f first

#define s second

#define pb push_back

#define mp make_pair

#define all(v) v.begin(),v.end()

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

ll power(ll x,ll y, ll md=inf){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}

 

using namespace std;





#define endl '\n'

#define int ll



signed main() {

	fast;



	int h,w;

	cin>>h>>w;



	pii v[200002];

	for(int i=0;i<h;i++) cin>>v[i].f>>v[i].s;



	map<int,int> mp;

	for(int i=1;i<=w;i++) mp[i] = 0;



	map<int, int> mini = {{0,w}};



	for(int i=0;i<h;i++) {

		int l = v[i].f;

		int r = v[i].s;



		auto it = mp.lower_bound(l);

		int mn = inf;



		while(it!=mp.end() && it->f <= r) {

			mn = min(mn, r+1-(it->f)+(it->s));

			auto it1 = it++;

			mini[it1->s]--;

			if(mini[it1->s]==0) mini.erase(it1->s);

			mp.erase(it1);

		}



		if(r+1<=w && mn<inf) {

			if(mp.count(r+1) && mp[r+1] > mn) {

				mini[mp[r+1]]--;

				if(mini[mp[r+1]]==0) mini.erase(mp[r+1]);

				mini[mn]++;

				mp[r+1] = mn;

			}

			else if(!mp.count(r+1)){

				mp[r+1] = mn;

				mini[mn]++;

			}

		}



		if(mini.size()) cout<<mini.begin()->f+i+1<<endl;

		else cout<<-1<<endl;



	}

}

// Faster C++ solution for the same problem (measured speedup: 1.6163408316389243x):
#include "bits/stdc++.h"

#define ll long long

#define lld long double

#define MOD 1000000007

#define inf 1000000007

#define pii pair<int,int>

#define f first

#define s second

#define pb push_back

#define mp make_pair

#define all(v) v.begin(),v.end()

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

// ll power(ll x,ll y, ll md=inf){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}

 

using namespace std;





#define endl '\n'

// #define int ll



signed main() {

	fast;



	int h,w;

	cin>>h>>w;



	pii v[200002];

	for(int i=0;i<h;i++) cin>>v[i].f>>v[i].s;



	map<int,int> mp;

	for(int i=1;i<=w;i++) mp[i] = 0;



	map<int,int> mini = {{0,w}};



	for(int i=0;i<h;i++) {

		int r = v[i].s;



		auto it = mp.lower_bound(v[i].f);





		if(r==w) {

			while(it!=mp.end() && it->f <= r) {

				auto it1 = it++;

				auto it2 = mini.find(it1->s);

				if(it2->s==1) mini.erase(it2);

				else it2->s --;

				mp.erase(it1);

			}

		}

		else {

			int mn = inf;



			while(it!=mp.end() && it->f <= r) {

				mn = min(mn, r+1-(it->f)+(it->s));

				auto it1 = it++;

				auto it2 = mini.find(it1->s);

				if(it2->s==1) mini.erase(it2);

				else it2->s --;

				mp.erase(it1);

			}



			if(mn<inf) {

				if(it!=mp.end() && it->f == r + 1) {

					if(it->s > mn) {

						auto it1 = mini.find(it->s);

						if(it1->s ==1) mini.erase(it1);

						else it1->s --;

						mini[mn]++;

						it->s = mn;

					}

				}

				else {

					mp.insert({r+1,mn});

					mini[mn]++;

				}

			}

		}



		if(mini.size()) cout<<mini.begin()->f+i+1<<endl;

		else cout<<-1<<endl;



	}

}
// Slower C++ solution:
#include "bits/stdc++.h"

#define ll long long

#define lld long double

#define MOD 1000000007

#define inf 1000000000000000000ll

#define pii pair<int,int>

#define f first

#define s second

#define pb push_back

#define mp make_pair

#define all(v) v.begin(),v.end()

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

ll power(ll x,ll y, ll md=inf){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}

 

using namespace std;





#define endl '\n'

#define int ll



signed main() {

	fast;



	int h,w;

	cin>>h>>w;



	pii v[200002];

	for(int i=0;i<h;i++) cin>>v[i].f>>v[i].s;



	map<int,int> mp;

	for(int i=1;i<=w;i++) mp[i] = 0;



	map<int,int> mini = {{0,w}};



	for(int i=0;i<h;i++) {

		int l = v[i].f;

		int r = v[i].s;



		auto it = mp.lower_bound(l);

		int mn = inf;



		while(it!=mp.end() && it->f <= r) {

			mn = min(mn, r+1-(it->f)+(it->s));

			auto it1 = it++;

			mini[it1->s]--;

			if(mini[it1->s]==0) mini.erase(it1->s);

			mp.erase(it1);

		}



		if(r+1<=w && mn<inf) {

			if(it!=mp.end() && it->f == r + 1) {

				if(it->s > mn) {

					mini[it->s]--;

					if(mini[it->s]==0) mini.erase(it->s);

					mini[mn]++;

					mp[r+1] = mn;

				}

			}

			else {

				mp[r+1] = mn;

				mini[mn]++;

			}

		}



		if(mini.size()) cout<<mini.begin()->f+i+1<<endl;

		else cout<<-1<<endl;



	}

}

// Faster C++ solution for the same problem (measured speedup: 1.6161931135723522x):
#include "bits/stdc++.h"

#define ll long long

#define lld long double

#define MOD 1000000007

#define inf 1000000007

#define pii pair<int,int>

#define f first

#define s second

#define pb push_back

#define mp make_pair

#define all(v) v.begin(),v.end()

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

// ll power(ll x,ll y, ll md=inf){ll res = 1;x%=md;while(y){if(y&1)res = (res*x)%md;x *= x; if(x>=md) x %= md; y >>= 1;}return res;}

 

using namespace std;





#define endl '\n'

// #define int ll



signed main() {

	fast;



	int h,w;

	cin>>h>>w;



	pii v[200002];

	for(int i=0;i<h;i++) cin>>v[i].f>>v[i].s;



	map<int,int> mp;

	for(int i=1;i<=w;i++) mp[i] = 0;



	map<int,int> mini = {{0,w}};



	for(int i=0;i<h;i++) {

		int r = v[i].s;



		auto it = mp.lower_bound(v[i].f);





		if(r==w) {

			while(it!=mp.end() && it->f <= r) {

				auto it1 = it++;

				auto it2 = mini.find(it1->s);

				if(it2->s==1) mini.erase(it2);

				else it2->s --;

				mp.erase(it1);

			}

		}

		else {

			int mn = inf;



			while(it!=mp.end() && it->f <= r) {

				mn = min(mn, r+1-(it->f)+(it->s));

				auto it1 = it++;

				auto it2 = mini.find(it1->s);

				if(it2->s==1) mini.erase(it2);

				else it2->s --;

				mp.erase(it1);

			}



			if(mn<inf) {

				if(it!=mp.end() && it->f == r + 1) {

					if(it->s > mn) {

						auto it1 = mini.find(it->s);

						if(it1->s ==1) mini.erase(it1);

						else it1->s --;

						mini[mn]++;

						it->s = mn;

					}

				}

				else {

					mp.insert({r+1,mn});

					mini[mn]++;

				}

			}

		}



		if(mini.size()) cout<<mini.begin()->f+i+1<<endl;

		else cout<<-1<<endl;



	}

}
// Slower C++ solution:
#include "bits/stdc++.h"

using namespace std;

typedef pair<int,int> pii;

#define rep(i,n) for(int i=0;i<(int)(n);i++)

#define all(a)  (a).begin(),(a).end()

#define pb push_back

#define INF 1<<30

#define MAX_V 200



struct edge{int to,cap,rev;};



vector<edge> G[10000];

bool used[10000];

void add_edge(int from,int to,int cap){

    G[from].pb((edge){to,cap,(int)G[to].size()});

    G[to].pb((edge){from,0,(int)(G[from].size())-1});

}



// ?¢?????????????DFS??§??¢???

int dfs(int v, int t, int f) {

    if (v == t) return f;

    used[v] = true;

    for (int i = 0; i < G[v].size(); i++) {

        edge &e = G[v][i];

        if (!used[e.to] && e.cap > 0) {

            int d = dfs(e.to, t, min(f, e.cap)); if (d > 0) {

                e.cap -= d;

                G[e.to][e.rev].cap += d;

                return d;

            }

        }

    }

    return 0;

}

// s??????t???????????§???????±???????

int max_flow(int s, int t) {

    int flow = 0; for (;;) {

        memset(used, 0, sizeof(used)); int f = dfs(s, t, INF);

        if (f == 0) return flow;

        flow += f;

    }

}



int main(){

    int v,e;

    cin>>v>>e;

    rep(i,e){

        int uu,vv,cc;

        cin>>uu>>vv>>cc;

        add_edge(uu,vv,cc);

    }

    cout<<max_flow(0,v-1)<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.2531806339913072x):
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)

#define all(a)  (a).begin(),(a).end()

#define pb push_back

#define INF (1e9+1)

//#define INF (1LL<<59)



#define MAX_V 100





// ????????¨???

struct edge{int to,cap,rev;};



vector<edge> G[MAX_V];  //??°???????????????

int level[MAX_V];       //?§??????????????????¢

int iter[MAX_V];        //???????????§????????????



// from??????to?????????????????????cap???????????°?????????????????????

void add_edge(int from,int to,int cap){

	G[from].push_back(  (edge){ to  ,cap,(int)G[to  ].size()   }  );

	G[to  ].push_back(  (edge){ from,0  ,(int)G[from].size()-1 }  );

}



// s????????????????????¢???BFS??§?¨??????????

void bfs(int s){

	rep(i,MAX_V)level[i]=-1;

	queue<int> que;

	level[s]=0;

	que.push(s);

	while(!que.empty()){

		int v=que.front();que.pop();

		

		rep(i,G[v].size()){

			edge &e=G[v][i];

			if(e.cap>0 && level[e.to]<0){

				level[e.to]=level[v]+1;

				que.push(e.to);

			}

		}

	}

}



//?¢?????????????DFS??§??¢???

int dfs(int v,int t,int f){

	if(v==t)return f;

	for(int &i=iter[v];i<G[v].size();i++){

		edge &e=G[v][i];

		if(e.cap>0&&level[v]<level[e.to]){

			int d=dfs(e.to,t,min(f,e.cap));

			if(d>0){

				e.cap-=d;

				G[e.to][e.rev].cap+=d;

				return d;

			}

		}

	}

	return 0;

}



// s??????t???????????§???????±???????

int max_flow(int s,int t){

	int flow=0;

	for(;;){

		bfs(s);

		if(level[t]<0)return flow;

		memset(iter,0,sizeof(iter));

		int f;

		while((f=dfs(s,t,INF))>0){

			flow+=f;

		}

	}

}





int main(){

	int v,e;

	cin>>v>>e;

	rep(i,e){

		int a,b,c;

		cin>>a>>b>>c;

		add_edge(a,b,c);

	}

	cout<<max_flow(0,v-1)<<endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define INF 1e9

#define MAX_V 10000

using namespace std;



//????????¨????§???????(???????????????????????????)

struct edge{int to, cap, rev;};



vector<edge> G[MAX_V]; //??°???????????£??\?????????

bool used[MAX_V];      //DFS??§?????§??????????????????????????°



//from??????to??????????????????cap???????????°?????????????????????

void add_edge(int from,int to,int cap){

  G[from].push_back((edge){to,cap,G[to].size()});

  G[to].push_back((edge){from,0,G[from].size()-1});  

}





//?¢?????????????DFS??§??¢???

int dfs(int v,int t,int f){

  if(v == t)return f;

  used[v]=true;

  for(int i=0; i<G[v].size() ;i++){

    edge &e = G[v][i];

    if(!used[e.to] && e.cap > 0){

      int d = dfs(e.to ,t , min(f,e.cap));

      if(d > 0){

	e.cap -= d;

	G[e.to][e.rev].cap += d;

	return d;

      }

    }

  }

  return 0;

}



//s??????t???????????§???????±???????

int max_flow(int s,int t){

  int flow = 0;

  for(;;){

    memset(used,0,sizeof(used));

    int f = dfs(s, t, INF);

    if(f == 0)return flow;

    flow += f;

  }

}





int main(){

  int n,m;

  cin>>n>>m;

  for(int i=0;i<m;i++){

    int u,v,c;

    cin>>u>>v>>c;

    add_edge(u,v,c);

  }

  cout<<max_flow(0,n-1)<<endl;



}

// Faster C++ solution for the same problem (measured speedup: 1.2197347696777732x):
#include <bits/stdc++.h>

#define MAX_V 1000

#define INF 1e9

using namespace std;



//????????¨????§???????(???????????????????????????)

struct edge{int to,cap,rev;};

vector<edge> G[MAX_V]; //??°???????????£??\???????????¨???

int level[MAX_V];      //s??????????????¢

int iter[MAX_V];       //???????????§??????????????£??????



//from??????to??????????????????cap???????????°??????????????????

void add_edge(int from,int to,int cap){

  G[from].push_back((edge){to,cap,G[to].size()});

  G[to].push_back((edge){from,0,G[from].size()-1});

}



//s????????????????????¢???BFS??§?¨??????????

void bfs(int s){

  memset(level,-1,sizeof(level));

  queue<int> que;

  level[s] = 0;

  que.push(s);

  while(!que.empty()){

    int v = que.front(); que.pop();

    for(int i=0; i<G[v].size(); i++){

      edge &e = G[v][i];

      if(e.cap > 0 && level[e.to] < 0){

	level[e.to] = level[v] + 1;

	que.push(e.to);

      }

    }

  }

}



//?¢?????????????DFS??§??¢??????

int dfs(int v,int t,int f){

  if(v==t) return f;

  for(int &i= iter[v]; i<G[v].size(); i++){

    edge &e = G[v][i];

    if(e.cap > 0 && level[v] < level[e.to]){

      int d = dfs(e.to, t, min(f, e.cap));

      if(d > 0){

	e.cap -= d;

	G[e.to][e.rev].cap += d;

	return d;

      }

    }

  }

  return 0;

}



//s??????t???????????§???????±???????

int max_flow(int s,int t){

  int flow=0;

  for(;;){

    bfs(s);

    if(level[t] < 0) return flow;

    memset(iter,0,sizeof(iter));

    int f;

    while((f=dfs(s ,t ,INF)) > 0 ) flow += f;

  }

}



int main(){

  int V,E;

  cin>>V>>E;



  for(int i=0;i<E;i++){

    int u,v,c;

    cin>>u>>v>>c;

    add_edge(u,v,c);

  }

  cout <<max_flow(0,V-1)<<endl;

}