Groups of Interest X51913

optilog

We want to configure the tables for a wedding. Every participant provides a list of topics of his/her interest. We assign a table such that everybody in the table shares (at least) one common topic.

Input

The input is a text (in the stdin) with the number of tables and a list of people and their topics of interest. For instance, the text:

2
Maria  politics SAT AI
John   art socker maths
Peter  socker art
Andrew bascket politics AI
Sara   art SAT maths
Holly  politics bascket

Output

The output is also a text (in the stdout) where, in every line, there is a list of components of one of the tables. In this example:

{ Sara John Peter }
{ Andrew Maria Holly }

Notice that the order of the lines and the order inside each line is not relevant.

If the problem has no solution, the program must print the text "No solution".

All tables have the same size (number of people). If the total number of people is not divisible by the number of tables, then all of them must have approximately the same number of participants. In other words, if n is the number of people and m is the number of tables, in every table we must seat either ⌊ n/m⌋ or ⌈ n/m⌉ people.

Scoring

Samples have been selected in order to ensure that there exists a unique solution up to people and tables permutations.

In the solution of this problem, you should use a function implemented for solving the "cardinality constraints" problem.

You will get 5 if you can solve the basic version of the problem where the number of people is divisible by the number of tables. You will get 5 additional points if you can also solve the case where the tables are not all of the same size (but their size only differs in one).