#P18417. Greedy Bipartite Matching

Greedy Bipartite Matching

Greedy Bipartite Matching

标准输入、标准输出。

给定一个有 2n2n 个顶点的带权二部图,左右两侧各有 nn 个顶点,两侧顶点分别编号为 11 到 nn。

称一个匹配为贪心匹配,当且仅当:在所有匹配中,它包含的权值为 11 的边最多;在满足此前条件的匹配中,它包含的权值为 22 的边最多;在继续满足此前全部条件的匹配中,它包含的权值为 33 的边最多;依此类推。也就是把匹配中各权值的边数按权值从小到大组成向量,使这个向量按字典序最大。

图会逐批加入边。请在加入每批边后,求当前图的贪心匹配的大小(边数)。

输入格式

第一行包含两个非负整数 n,qn,q(n≤105n\le10^5,q≤103q\le10^3),分别表示二部图每侧的顶点数和不同边权的个数。

接下来有 qq 个块。第 ii 个块先给出一个非负整数 mim_i,表示权值为 ii 的边数。随后 mim_i 行,每行两个整数 x,yx,y(1≤x,y≤n1\le x,y\le n),表示在左侧顶点 xx 和右侧顶点 yy 之间加入一条边。

保证 ∑i=1qmi≤2⋅105\sum_{i=1}^{q}m_i\le2\cdot10^5。

两个顶点之间可以有多条边,包括同权和不同权的重边。

输出格式

在一行中输出 qq 个整数:依次表示仅考虑权值不超过 1,2,…,q1,2,\ldots,q 的边时,贪心匹配的大小。

q=0q=0 时没有需要输出的整数,允许输出为空。n=0n=0 时所有 mim_i 必须为 00。

样例

3 4
2
1 1
1 2
2
1 1
2 2
2
1 3
3 2
1
3 3
1 2 2 3