题目描述

这是一道模板题。

给定一个正则二分图 $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$。