Times

Chegou a hora da caça ao tesouro na gincana escolar! Para jogar, sua turma de $N$ pessoas deve se dividir em dois times. A divisão será feita com base no número de chamada de cada aluno, um número entre $1$ e $N$. Só que mais importante que fazer uma divisão balanceada é evitar que pessoas que não se gostam fiquem no mesmo time. Você receberá o número $N$ de alunos e, para cada pessoa, você receberá a lista de pessoas que ela não gosta. Se a pessoa $A$ não gosta da pessoa $B$ então a pessoa $B$ também não gosta da pessoa $A$. O aluno de número $1$ sempre ficará no primeiro time. Você deve dividir os outros alunos entre os dois times de forma que dentro de cada time não haja duas pessoas que não se gostam.

Entrada

A primeira linha contém um inteiro $N$, representando o número de alunos na turma. As $N$ linhas seguintes, para $1 \leq i \leq N$, contém um inteiro $M_i$, indicando de quantas pessoas o aluno $i$ não gosta, e em seguida $M_i$ inteiros $X_j$, indicando que a pessoa $i$ não gosta da pessoa $X_j$.

Saída

Seu programa deve produzir duas linhas, a primeira contendo os números dos integrantes do primeiro time e a segunda contendo os números dos integrantes do segundo time, ambas em ordem crescente. Lembre-se que o aluno $1$ sempre estará no primeiro time. Sempre há uma única solução.

Restrições

• $2 \leq N \leq 10^5$.
• $1 \leq M_i \leq N - 1$.
• $1 \leq X_j \leq N$.
• $1\leq \sum_{i = 1}^N M_i \leq 6 \times 10^5$.
• Ou seja, a soma de todos os $M_i$ descritos na entrada é no máximo $6 \times 10^5$.

Informações sobre a pontuação

• Em um conjunto de casos de teste equivalente a $40$ pontos, $N \leq 15$.

Exemplos

Exemplo de entrada 1

13
2 12 9
1 10
3 8 12 13
5 8 10 13 6 5
2 11 4
1 4
1 8
3 4 3 7
1 1
2 2 4
1 5
2 3 1
2 4 3

Exemplo de saída 1

1 2 3 4 7 11
5 6 8 9 10 12 13

Exemplo de entrada 2

15
1 13
1 13
1 13
1 13
1 13
1 13
1 13
1 13
1 13
1 13
1 13
1 13
14 11 7 1 10 8 6 14 12 3 2 15 5 4 9
1 13
1 13

Exemplo de saída 2

1 2 3 4 5 6 7 8 9 10 11 12 14 15
13