{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/AUG14/mandarin/PUSHFLOW.pdf\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/AUG14/russian/PUSHFLOW.pdf\"\u003eRussian\u003c/a\u003e.\u003c/h3\u003e\n\n\u003cp\u003e\nYou are given a connected undirected graph \u003cb\u003eG\u003c/b\u003e, consisting of \u003cb\u003eN\u003c/b\u003e vertices and \u003cb\u003eM\u003c/b\u003e edges. The vertices of \u003cb\u003eG\u003c/b\u003e are indexed with integers 1, 2, 3, ..., \u003cb\u003eN\u003c/b\u003e, the edges of \u003cb\u003eG\u003c/b\u003e are indexed with integers 1, 2, 3, ..., \u003cb\u003eM\u003c/b\u003e. Each edge of \u003cb\u003eG\u003c/b\u003e has \u003ci\u003ea capacity\u003c/i\u003e - a positive integer parameter. Each pair of the vertices is connected by at most one edge. No edge connects a vertex with itself.\n\u003c/p\u003e\n\n\u003cp\u003e\nLet\u0027s call a sequence of vertices \u003cb\u003eA\u003c/b\u003e \u003d \u003cb\u003eA\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eA\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ..., \u003cb\u003eA\u003csub\u003eK\u003c/sub\u003e\u003c/b\u003e(\u003cb\u003eK\u003c/b\u003e \u003e 2) \u003ci\u003ea simple cycle\u003c/i\u003e, if:\n\u003c/p\u003e\n\n\u003cp\u003e\n \u003cul type\u003d\"square\"\u003e\n \u003cli\u003eThere\u0027s an edge between vertices \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb\u003eA\u003csub\u003ei + 1\u003c/sub\u003e\u003c/b\u003e, for each 1 ≤ \u003cb\u003ei\u003c/b\u003e \u003c \u003cb\u003eK\u003c/b\u003e;\n \u003cli\u003eThere\u0027s an edge between vertices \u003cb\u003eA\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e and \u003cb\u003eA\u003csub\u003eK\u003c/sub\u003e\u003c/b\u003e; \n \u003cli\u003e\u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e equals to \u003cb\u003eA\u003csub\u003ej\u003c/sub\u003e\u003c/b\u003e if and only if \u003cb\u003ei\u003c/b\u003e equals to \u003cb\u003ej\u003c/b\u003e.\n \u003c/ul\u003e\n\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed, that each vertex of \u003cb\u003eG\u003c/b\u003e belongs to at most one simple cycle.\u003c/p\u003e\n\n\u003cp\u003eYou task is to implement a data structure, which can process the following queries efficiently:\u003c/p\u003e\n\n\u003cp\u003e\n \u003cul type\u003d\"square\"\u003e\n \u003cli\u003e0 \u003cb\u003eS\u003c/b\u003e \u003cb\u003eT\u003c/b\u003e: find the maximum flow in \u003cb\u003eG\u003c/b\u003e in case the source is \u003cb\u003eS\u003c/b\u003e and the sink is \u003cb\u003eT\u003c/b\u003e;\n \u003cli\u003e1 \u003cb\u003eX\u003c/b\u003e \u003cb\u003eNEW_CAPACITY\u003c/b\u003e: make the capacity of \u003cb\u003eX\u003c/b\u003e\u0027th edge equal to \u003cb\u003eNEW_CAPACITY\u003c/b\u003e. \n \u003c/ul\u003e\n\u003c/p\u003e\n\n\u003cp\u003eYou can read about maximum flow problem here: \u003ca href\u003d\"http://en.wikipedia.org/wiki/Maximum_flow_problem\"\u003ehttp://en.wikipedia.org/wiki/Maximum_flow_problem\u003c/a\u003e\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003e \u003c/p\u003e \n\u003cp\u003eThe first line of the input contains two integers \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eM\u003c/b\u003e, denoting the number of the vertices and the number of the edges.\u003c/p\u003e\n\u003cp\u003eThe next \u003cb\u003eM\u003c/b\u003e lines contain the information about the edges of \u003cb\u003eG\u003c/b\u003e, each contains three integers \u003cb\u003eU\u003c/b\u003e, \u003cb\u003eV\u003c/b\u003e and \u003cb\u003eC\u003c/b\u003e, which means that this edge connects vertices \u003cb\u003eU\u003c/b\u003e-\u003cb\u003eV\u003c/b\u003e and has a capacity equal to \u003cb\u003eC\u003c/b\u003e. The information about \u003cb\u003ei\u003c/b\u003e\u0027th edge is on \u003cb\u003e(i + 1)\u003c/b\u003e\u0027th line of the input.\u003c/p\u003e\n\u003cp\u003eThe next line contains an integer \u003cb\u003eQ\u003c/b\u003e, denoting the number of queries to process.\u003c/p\u003e\n\u003cp\u003eThe next \u003cb\u003eQ\u003c/b\u003e lines contain the queries to process, each contains one query. The format of queries is the same with the one described in the legend.\u003c/p\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eYour output should contain exactly \u003cb\u003eQ\u003csub\u003e0\u003c/sub\u003e\u003c/b\u003e lines, where \u003cb\u003eQ\u003csub\u003e0\u003c/sub\u003e\u003c/b\u003e is the number of the queries of the zeroth type in the input.\u003c/p\u003e\n\u003cp\u003eFor 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.\u003c/p\u003e\n\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 100 000;\u003c/li\u003e\n\u003cli\u003e0 ≤ \u003cb\u003eM\u003c/b\u003e ≤ 200 000;\u003c/li\u003e\n\u003cli\u003e0 ≤ \u003cb\u003eQ\u003c/b\u003e ≤ 200 000;\u003c/li\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eU, V\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e, for each edge;\u003c/li\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eC\u003c/b\u003e ≤ 10\u003csup\u003e9\u003c/sup\u003e, for each edge;\u003c/li\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eS ≠ T\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e, for each query of the zeroth type appeared in the input;\u003c/li\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eX\u003c/b\u003e ≤ \u003cb\u003eM\u003c/b\u003e, for each query of the first type appeared in the input;\u003c/li\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eNEW_CAPACITY\u003c/b\u003e ≤ 10\u003csup\u003e9\u003c/sup\u003e, for each query of the first type appeared in the input;\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003e \u003c/p\u003e\n\u003ch3\u003eExample\u003c/h3\u003e\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\n6 6\n1 2 1\n4 5 8\n4 3 2\n6 5 5\n1 6 4\n2 3 1\n6\n0 4 5\n0 1 3\n0 1 2\n1 1 5\n1 6 5\n0 1 2\n\n\u003cb\u003eOutput:\u003c/b\u003e\n9\n3\n2\n7\n\u003c/pre\u003e\n\u003cp\u003e \u003c/p\u003e"}}]}