description
给定 (n imes m) 的网格图，有些格子有障碍，无障碍且相邻的格子之间连边形成图。保证 ((1, 1)) 无障碍，保证无障碍格子连通。
将网格图黑白染色，相邻格子颜色不同，((1,1)) 为黑色。
构造一棵生成树，使得以 ((1,1)) 为根时，所有叶子都为白色。注意：即使 ((1,1)) 度数为 (1)，也不能视为叶子。
solution
拟阵交。
注意到黑白染色后，每条边最多属于一个黑点，因此可以构造边拟阵 (I_1) 表示删除独立集 (P) 的边后，剩下的黑点相邻的边数 (geq 2)（注意反过来加边不能构成拟阵，删边才可以）。这里需要特判初始时黑点度数是否 (geq 2)。
另一个拟阵 (I_2) 就可以套路地构造成图拟阵的对偶拟阵即可。求出最大拟阵交，检验是否为生成树。
至于怎么求拟阵交，可以参考 2018 年集训队论文《浅谈拟阵的一些拓展及其应用 —— 江苏省淮阴中学 杨乾澜》。
submission
details
放两个参考资料，这里有一份题单，这里有一份简单的拟阵 & 拟阵交算法介绍。
简单写个拟阵交算法的流程（当然，没有证明）：类似于二分图匹配，构造 (X) 部表示已在拟阵交的，(Y) 部表示未在拟阵交的。
对于所有 (uin Y)，当 (Xcup uin I_1)，建边 ((s, u))；当 (Xcup u in I_2)，建边 ((u, t))。
对于所有 (uin Y,vin X)，当 ((Xsetminus v)cup u in I_1)，建边 ((v,u))；当 ((X setminus v)cup uin I_2)，建边 ((u,v))。
那么一条 (s o t) 的最短增广路翻转后，总可以得到更大的拟阵交。
如果带权，则给 (X) 部的点权 (-v)，给 (Y) 部的点权 (v)，跑以点权和最大为第一关键字，以边数最少为第二关键字找 (s o t) 的增广路。如果直接跑 spfa(bellman) 则一定是边数最少。