Tournament Match Scheduling

In this problem, you are given n employees who will participate in a tournament over k rounds. In each round, every employee must participate in exactly one match, forming n/2 pairs. However, some matches (pairs) have already been played and cannot be repeated.

You are required to schedule k rounds such that:

( \bullet ) No match is repeated (i.e. a pair that has played before or appears in earlier rounds should not be scheduled again). ( \bullet ) In every round, each employee plays exactly once (so exactly n/2 matches occur in a round).

If it is not possible to produce such a schedule, output the string "Not possible". Otherwise, output k lines where each line represents a round. In each round, output n integers where every two consecutive integers form a match. Note that matches are represented as pairs (a, b) with ( a < b ) and the order of rounds or matches does not matter as long as the constraints are met.

The input and output formats for the competitive problem are detailed below.

inputFormat

The first line contains three integers: (n), (m), and (k) where (n) is the number of employees, (m) is the number of matches that have already been played, and (k) is the number of rounds to schedule. Each of the following (m) lines contains two integers representing the employees in a previously played match.

outputFormat

If a valid schedule exists, output exactly (k) lines. Each line must contain (n) space-separated integers where every pair of consecutive integers represents a match for that round. If no valid schedule exists, output the string "Not possible".## sample

4 2 2
1 2
3 4

1 3 2 4
1 4 2 3