Pirate Gang and Coin Distribution

Consider the following situation: if pirate A and pirate B are friends, and pirate B and pirate C are friends then they all belong to the same gang. You are given x friendship (brotherhood) relationships among pirates. Using these relationships, you must determine the gang structure among the n pirates.

After that, you are also given that m coins are to be distributed among the n pirates. The distribution method should be lexicographically maximum under the constraint that each pirate receives at least one coin and the distribution is non‐increasing, i.e. pirates with smaller numbers (IDs) should receive as many coins as possible, even if that breaks the natural gang boundaries.

More formally, let the distribution be an array \(a_1, a_2, \ldots, a_n\) such that \(a_i \ge 1\) for all i and \(a_1 \ge a_2 \ge \cdots \ge a_n\). Among all such arrays with \(\sum_{i=1}^n a_i = m\), choose the one which is lexicographically maximum.

You are required to first compute the gang relationships using the given friendship relations. Then, output the following:

• The total number of gangs.
• For each gang, output the list of pirates (by their IDs) in the gang in ascending order. The gangs themselves should be ordered by the smallest pirate number in each gang.
• A single line containing the coin distribution for pirates from pirate 1 to pirate n. Note that the lexicographically maximum solution is unique: it assigns pirate 1 exactly \(m-(n-1)\) coins while every other pirate gets exactly 1 coin.

Note: You may assume that \(m \ge n\) always holds.

inputFormat

The first line contains three integers x, n and m where:

• x: the number of friendship relationships.
• n: the total number of pirates (numbered from 1 to n).
• m: the total number of coins.

Each of the next x lines contains two integers u and v indicating that pirate u and pirate v are friends (and hence in the same gang, directly or indirectly).

outputFormat

Output should consist of several lines:

1. The first line contains the total number of gangs.
2. For the next several lines, for each gang (sorted by the smallest pirate id in the gang), output the members of the gang in ascending order separated by a single space.
3. The last line contains n integers representing the coin distribution for pirates 1 through n (the lexicographically maximum distribution, where pirate 1 gets \(m-(n-1)\) coins and every other pirate gets 1 coin).

sample

2 5 10
1 2
4 5

3
1 2
3
4 5
6 1 1 1 1