QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 2048 MB Total points: 100
[+3]

# 265. 正则二分图匹配

Statistics

题目描述

这是一道模板题。

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

输入格式

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

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

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

输出格式

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

样例数据

样例输入

4 2
3 4
1 3
2 2
1 4

样例输出

4 3 2 1

子任务

对于 30% 的数据,保证 n×d2×105

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

对于 100% 的数据,保证 n×d2×106