uCoder | 1092 | Nível: 4 | Tempo Limite: 10
Escalonamento de salas de aula
Adaptado por Erich Rodrigues
Competição: USP - Seletiva para Maratona de Programação, 2013
Os professores da Universidade de Ecaterimburgo não gostam de deslocar-se por longas distâncias. Cada docente deseja que as salas em que ele vai dar aula estejam em posições adjacentes. No início de cada semestre cabe ao responsável pela Comissão de Graduação determinar as salas de aula em que os docentes deverão dar aula. Cada docente sabe que turma de alunos deverá assistir às suas aulas como, por exemplo, alunos do terceiro período de Engenharia Mecânica, ou alunos do primeiro período de Computação, etc. Os alunos de cada turma permanecem na mesma sala em todas as aulas. O importante é que todas as salas em que um docente dá aulas fiquem em posições adjacentes. Nem sempre é possível satisfazer os requisitos dos docentes. Se, por exemplo, um docente dá aulas para o terceiro semestre de Matemática e primeiro semestre de Computação, um segundo dá aulas para o primeiro semestre de Computação e segundo período de Engenharia Elétrica e um terceiro professor dá aulas para os alunos do segundo período de Engenharia Elétrica e terceiro semestre de Matemática, claramente não é possível satisfazer os três professores. Sua tarefa é ajudar o responsável pela alocação das salas, e determinar se é possível satisfazer todos os requisitos dos docentes.
Entrada
A entrada é composta por diversas instâncias e termina com final de arquivo (EOF).
Na primeira linha de cada instância é dado o número de turmas T , numeradas de 1 a T , e o número de docentes D. Nas D linhas seguintes são dados o número K de turmas em que o docente correspondente dá aulas seguido pelas identificações destas turmas em ordem crescente.
A entrada deve ser lida da entrada padrão.
Saída
Para cada instância o seu programa deverá imprimir uma permutação das turmas que atenda os requisitos de todos os docentes, ou seja, todas as turmas em que um docente dá aula estejam adjacentes. Caso não exista uma tal permutação seu programa deverá imprimir impossivel. Se existir mais de uma permutação possível, qualquer uma será aceita.
A saída deve ser escrita na saída padrão.
Restrições
• 1 ≤ T ≤ 10³
• 1 ≤ D ≤ 10³
• 0 ≤ K ≤ T
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
5 4 |
4 2 5 1 3 |