URI Online Judge | 2112

Scheduling Classrooms

By XVII Maratona de Programação IME-USP, 2013 BR Brazil

Timelimit: 1

Yekaterinburg University teachers don't like to travel over long distances. Each teacher want the rooms in which he will teach are in adjacent positions. At the beginning of each semester the Graduate Committee responsible for determining the classrooms in which teachers should teach. Every teacher knows that classroom of students should attend his lectures as, for example, students in the third period of mechanical engineering, or students of the first Computation, etc. The students of each class remain in the same room in every class. The important thing is that all the rooms where a teacher teaches are in adjacent positions. It is not always possible to meet the requirements of teachers. If, for example, a faculty member teaches for the third semester of mathematics and computing, a first half second teaches for the first half of computing and electrical engineering second sentence and a third teacher gives lessons to the students of the second period of electrical engineering and third semester of Math, clearly it is not possible to satisfy the three teachers. Your task is to help the responsible for allocating rooms, and determine whether it is possible to satisfy all the requirements of teachers.


The entrance is composed of various bodies and ends with end-of-file (EOF). In the first line of each instance is given the number of classes T (1 < T < 103), numbered from 1 to T, and the number of professors d. In D (1 < D < 103) next lines are given the number K (0 < K < T)of classes in which the teacher teaches correspondent followed by IDs of these groups in ascending order.


For each instance your program should print a permutation class that meets the requirements of all teachers, i.e. every class where a teacher teaches are adjacent. If there is no such permutation your program should print "impossivel". If there is more than one possible permutation, any one is accepted.

Sample Input Sample Output

5 4
3 2 4 5
2 2 5
2 1 5
2 1 3
3 3
2 1 2
2 2 3
2 1 3

4 2 5 1 3