URI Online Judge | 2429

Rodovia

Por OBI - Olimpíada Brasileira de Informática 2013 BR Brazil

Timelimit: 1

As estradas da Nlogônia estão severamente danificadas, devido ao intenso fluxo de veículos pesados criado pelo desenvolvimento econômico do reino. Para resolver o problema, o rei da Nlogônia decretou que seriam construídas novas rodovias. O decreto determinou que:

O engenheiro-chefe do reino desenhou uma proposta de mapa viário; o rei verificou que o plano satisfaz as três primeiras restrições, mas não conseguiu verificar a última. Por isso, ele pediu que você escrevesse um programa que determina se o plano de rodovias permite viajar de qualquer cidade até qualquer outra cidade da Nlogônia.

Entrada

A primeira linha de cada caso de teste contém um inteiro (2 ≤ N ≤ 104), indicando o número de cidades. Cada uma das N linhas seguintes descrevem uma estrada: a linha contém dois inteiros A e B (A ≠ B)que indicam que existe uma estrada de mão única ligando a cidade A a outra cidade, B (as cidades são numeradas de 1 a N).

Saída

Imprima uma única linha contendo um único caractere: ‘S’ se for possível ir de qualquer cidade a qualquer outra cidade por rodovias e ‘N’ caso contrário.

Exemplos de Entrada Exemplos de Saída

3

1 2

2 3

3 1

S

3

1 2

2 3

1 3

N

6

1 2

2 3

4 1

5 6

3 5

6 4

S

6

1 2

2 3

3 1

4 5

5 6

6 4

N