[AdditionalFile180.zip](file://AdditionalFile180.zip?type=additional_file)

#180. 正则二分图匹配

标签: 传统 | 时间限制: 6000 ms | 内存限制: 512 MiB 通过: 121 | 提交: 234

题目描述

这是一道模板题。

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

输入格式

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

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

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

输出格式

输出一行 $n$ 个整数，是一个 $1, \dots, n$ 的排列，表示一个完美匹配，设 $p_i = j$，表示 $x_i$ 向 $y_j$ 连边为匹配中的一条。

样例

输入

4 2
3 4
1 3
2 2
1 4

输出

4 3 2 1

数据范围与提示

对于 30% 的数据，保证 $n \times d \le 2 \times 10^5$。

对于另外 30% 的数据，保证 $d$ 是 2 的整次幂。

对于 100% 的数据，保证 $n \times d \le 2 \times 10^6$。