题目描述
这是一道模板题。
给定一个正则二分图 G=(X,Y,E),其中 |X|=|Y|=n 且每个点的度数均为 d,请你求出一个其完美匹配。
输入格式
第一行输入两个正整数 n,d,意义如题目描述所示。
接下来 n 行每行输入 d 个正整数,其中第 i+1 行若输入一个正整数 j 则表示 xi 与 yj 连一条边。图中可能有重边。
保证给出的图是 d-正则图。
输出格式
输出一行 n 个整数,是一个 1,…,n 的排列,表示一个完美匹配,设 pi=j,表示 xi 向 yj 连边为匹配中的一条。
样例数据
样例输入
4 2
3 4
1 3
2 2
1 4
样例输出
4 3 2 1
子任务
对于 30% 的数据,保证 n×d≤2×105。
对于另外 30% 的数据,保证 d 是 2 的整次幂。
对于 100% 的数据,保证 n×d≤2×106。