Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QUEIMG14 - Ferrovia do Pão de Queijo

Com a proximidade da Copa do Mundo, o governo estuda a possibilidade de construir um sistema de transporte ferroviário entre algumas cidades de Minas: a Ferrovia do Pão de Queijo. O sistema tem o objetivo de garantir que o estoque de Pão de Queijo dos cafés do estado não se esgote durante a competição.

A ideia chamou a atenção de muitos mineiros, que inundaram o governo com várias propostas para a construção do sistema. Cada proposta contém uma lista de estações, cada qual descrita por um conjunto de linhas de trem.

Dizemos que duas dessas estações U e V estão conectadas se houver uma sequência de estações S1,...,Sk tais que S1 = U, Sk = V e todo par de estações adjacentes (Si, Si+1) tem pelo menos uma linha de trem em comum. Uma proposta é dita conectada se todo par de estações da proposta for conectado.

É desejável que o Pão de Queijo possa fluir entre qualquer par de estações. Em função disso, o governo decidiu rejeitar todas as propostas de sistema de transporte que não forem conectadas. Nesse problema, você deve escrever um programa que identifica se uma proposta de sistema de transporte é conectada.

Entrada

A entrada possui múltiplos casos de teste. Cada caso de teste começa com uma linha contendo dois inteiros N, K.

$N é o número de estações de trem (1 ≤ N ≤ 105) K é o número de linhas de trem (1 ≤ K ≤ 10)

Em seguida, há N linhas contendo as linhas de trem que passam por cada estação. Cada uma dessas linhas começa com um inteiro ni que indica o número de linhas de trem da estação i (0 ≤ ni ≤ K). Em seguida, na mesma linha, há ni números inteiros distintos ei1, ..., ei ni, que indicam as linhas de trem que passam na estação i (1 ≤ eij ≤ K).

A entrada termina com N=K=0.

Saída

Para cada caso de teste, imprima uma única linha contendo o caractere “S” caso o conjunto de estações de trem seja conectado e o caractere “N” caso contrário. Os caracteres devem ser impressos em letras maiúsculas e sem aspas.

Exemplos

Entrada:
5 10
3 8 7 6
3 6 8 7
3 7 8 6
3 6 7 8
3 8 6 7
6 5
3 4 2 3
2 5 1
2 4 3
2 5 1
2 4 3
2 1 5
0 0

Saída:
S
N

Adicionado por:Wanderley Guimarăes
Data:2014-07-10
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Maratona Mineira 2014

hide comments
2014-07-23 06:54:44 Jeferson Lesbão de Siqueira[UNITAU]
Esta tudo ok com o tempo limite desse problema ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.