#1615. 正则二分图匹配

正则二分图匹配

题目描述

这是一道模板题。

给定一个正则二分图 G=(X,Y,E)G=(X,Y,E),其中 X=Y=n|X|=|Y|=n 且每个点的度数均为 dd,请你求出一个其完美匹配。

输入格式

第一行输入两个正整数 n,dn,d,意义如题目描述所示。

接下来 nn 行每行输入 dd 个正整数,其中第 i+1i+1 行若输入一个正整数 jj 则表示 xix_iyjy_j 连一条边。图中可能有重边

保证给出的图是 dd-正则图。

输出格式

输出一行 nn 个整数,是一个 1,,n1,\dots,n 的排列,表示一个完美匹配,设 pi=jp_i=j,表示 xix_iyjy_j 连边为匹配中的一条。

样例

4 2
3 4
1 3
2 2
1 4

4 3 2 1

数据范围与提示

对于 30%30\% 的数据,保证 n×d2×105n\times d\le 2\times 10^5

对于另外 30%30\% 的数据,保证 dd22 的整次幂。

对于 100%100\% 的数据,保证 n×d2×106n\times d\le 2\times 10^6