#P6942. [2018年5月雅礼集训]桥
[2018年5月雅礼集训]桥
桥
Time Limit: 1.5s
Memory Limit: 256MB
Description
有一张的网格图, 初始时其中有 条边.

图1: 时的初始网格。坐标第一维为行(1或2),第二维为列(1到 ),初始连接所有上下、左右相邻点。
现在给出次操作, 操作分为两类:
-
1 x0 y0 x1 y1加入 到 的边. -
2 x0 y0 x1 y1删除 到 的边.
每次操作结束后输出图中桥边的数量, 这里的桥边指删除后会使联通块数量增加的边.
Input Format
输入数据第一行包含两个空格隔开的正整数.
接下来行, 每行描述一次操作.
Output Format
输出 M 行, 每行一个数, 表示当前图中桥边的数量.
Sample
样例0输入
4 8
2 1 3 2 3
2 1 2 2 2
2 1 4 2 4
1 1 2 2 2
1 1 3 2 3
2 1 1 2 1
1 1 4 2 4
2 2 2 2 3
样例0输出
0
0
7
4
2
4
2
4
Input1
见下发样例 /bridge/bridge1.in.
Output1
见下发样例 /bridge/bridge1.ans.
Constraints
对于 20% 的数据, .
对于另外 40% 的数据, 只有删边操作.
对于 100% 的数据, , , 加边和删边操作合法, .