Regular matching
Maxim has been captivated by graph theory since he was a child. Currently, he is particularly interested in bipartite graphs. A bipartite graph is one where the vertices can be divided into two sets, with no edges connecting vertices within the same set. In a fascinating book, Maxim learned that a regular bipartite graph has a perfect matching. The book also explained that a regular graph is one where all vertices have the same degree, and a perfect matching is a way to pair all vertices such that each pair is connected by an edge. However, the book didn't describe how to find this matching. Maxim spent the whole night searching for an algorithm, only to discover a brief note in a large book stating that this problem is easily solved for bipartite regular graphs with a degree of 2k. Help him find the perfect matching.
Input
The first line contains the integer n (1 ≤ n ≤ 50000) — the number of vertices in each part of the graph. The second line contains the degree d of each vertex (d = 2k, where 0 ≤ k ≤ 5). The next n lines each contain d integers, representing the vertices in the second part that are adjacent to each vertex in the first part. The vertices in both parts are independently numbered from 1 to n. The graph may have multiple edges, meaning a pair of vertices can be connected by more than one edge. It is guaranteed that all vertices in both parts have the same degree d.
Output
Output exactly n integers — for each vertex in the first part, specify the vertex in the second part with which it is paired in a perfect matching. The output should be a permutation of the numbers from 1 to n. If multiple solutions exist, you may output any one.