Push the Flow!

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given a connected undirected graph G, consisting of N vertices and M edges. The vertices of G are indexed with integers 1, 2, 3, ..., N, the edges of G are indexed with integers 1, 2, 3, ..., M. Each edge of G has a capacity  a positive integer parameter. Each pair of the vertices is connected by at most one edge. No edge connects a vertex with itself.
Let's call a sequence of vertices A = A_{1}, A_{2}, ..., A_{K}(K > 2) a simple cycle, if:
 There's an edge between vertices A_{i} and A_{i + 1}, for each 1 ≤ i < K;
 There's an edge between vertices A_{1} and A_{K};
 A_{i} equals to A_{j} if and only if i equals to j.
It's guaranteed, that each vertex of G belongs to at most one simple cycle.
You task is to implement a data structure, which can process the following queries efficiently:
 0 S T: find the maximum flow in G in case the source is S and the sink is T;
 1 X NEW_CAPACITY: make the capacity of X'th edge equal to NEW_CAPACITY.
You can read about maximum flow problem here: http://en.wikipedia.org/wiki/Maximum_flow_problem
Input
The first line of the input contains two integers N and M, denoting the number of the vertices and the number of the edges.
The next M lines contain the information about the edges of G, each contains three integers U, V and C, which means that this edge connects vertices UV and has a capacity equal to C. The information about i'th edge is on (i + 1)'th line of the input.
The next line contains an integer Q, denoting the number of queries to process.
The next Q lines contain the queries to process, each contains one query. The format of queries is the same with the one described in the legend.
Output
Your output should contain exactly Q_{0} lines, where Q_{0} is the number of the queries of the zeroth type in the input.
For each query of the zeroth type you should to output one integer: the maximum flow in the corresponding graph. You should output the answers for the queries in the order they appear in the input.
Constraints
 1 ≤ N ≤ 100 000;
 0 ≤ M ≤ 200 000;
 0 ≤ Q ≤ 200 000;
 1 ≤ U, V ≤ N, for each edge;
 1 ≤ C ≤ 10^{9}, for each edge;
 1 ≤ S ≠ T ≤ N, for each query of the zeroth type appeared in the input;
 1 ≤ X ≤ M, for each query of the first type appeared in the input;
 1 ≤ NEW_CAPACITY ≤ 10^{9}, for each query of the first type appeared in the input;
Example
Input: 6 6 1 2 1 4 5 8 4 3 2 6 5 5 1 6 4 2 3 1 6 0 4 5 0 1 3 0 1 2 1 1 5 1 6 5 0 1 2 Output: 9 3 2 7
Author:  kostya_by 
Editorial  http://discuss.codechef.com/problems/PUSHFLOW 
Tags  aug14, graphs, hard, heavylight, kostya_by, tree 
Date Added:  27062014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 