Team Formation with Common Skills

In a company, each of the n employees possesses a set of skills. Two employees can be directly connected if they share at least one common skill. A project team is valid only if every employee is connected directly or indirectly with every other employee in the team via some common skill. Given the list of employees and their skills, your task is to decide whether it is possible to form a fully connected project team.

If it is possible, output a list of connections in the form of triples (a, b, c) where a and b represent the 1-indexed employee numbers that are directly connected via the skill c. The connections should form a spanning tree over the employees (i.e. exactly n-1 edges if they are all connected). If the team cannot be connected, print the string (\texttt{impossible}).

The problem can be modeled by a graph where vertices represent employees and there is an edge between two employees if they share a common skill. A successful connection means that the graph is connected.

inputFormat

Input is read from standard input. The first line contains an integer (n) ( (1 \le n \le 10^5)) representing the number of employees. This is followed by (n) lines. The (i)-th line describes the (i)-th employee and starts with an integer (k_i) indicating the number of skills that the employee has, followed by (k_i) integers representing the skills. Skills are represented by positive integers.

outputFormat

If it is possible to connect all the employees, print exactly (n-1) lines, each containing three integers (a), (b), and (c) separated by spaces, which denote that employee (a) and employee (b) are connected by the common skill (c). The connections must form a spanning tree. If it is not possible, print a single line containing the word (impossible).## sample

5
3 100 200 300
2 300 400
3 500 200 600
1 100
2 400 500

1 4 100
1 3 200
1 2 300
2 5 400