SPOJ Brasil

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 S₁,...,S_k tais que S₁ = U, S_k = V e todo par de estações adjacentes (S_i, S_i+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 ≤ 10⁵) 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 n_i que indica o número de linhas de trem da estação i (0 ≤ n_i ≤ K). Em seguida, na mesma linha, há n_i números inteiros distintos e_i1, ..., e_{i ni}, que indicam as linhas de trem que passam na estação i (1 ≤ e_ij ≤ 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