13579번 - Série de Tubos

O ano é 2010. O espetacular resultado de um projeto ultra-secreto, iniciado três anos antes por um grupo de pesquisadores da SBC (Soluções Brasileiras em Cabeamento) está prestes a ser divulgado: a SBC conseguiu a proeza de transportar matéria através de cabos de fibra ótica! A pesquisa contraria a famosa e polêmica frase do ex-senador e atual presidente dos EUA, que na época do início da pesquisa, há três anos, afirmara que "a internet não é como um caminhão de carga, em que você despeja o que quiser; a internet na verdade é uma série de tubos". Com isso, a SBC, que atualmente aluga a sua rede de cabos para uma operadora de TV paga, pensa em mudar de negócio e iniciar-se na atividade de transporte de carga -- apesar de a tecnologia desenvolvida servir também para o transporte de seres vivos, há dificuldades políticas na homologação desse meio de transporte para seres humanos.

A rede de fibra ótica da SBC cobre todas as capitais do país. A rede é composta por ramos de fibra ótica e concentradores. Há um concentrador em cada capital, e um ramo de fibra ótica conecta diretamente um par de concentradores. Nem todo concentrador está conectado diretamente por um ramo de fibra a todos os outros concentradores, mas a rede é conexa. Ou seja, a partir de um dado concentrador existe uma seqüência de ramos e concentradores que permite que uma informação gerada em qualquer um dos concentradores pode ser enviada a qualquer outro concentrador da rede.

Para comunicação de dados, é normal que um ramo de fibra ótica possa ser utilizado para enviar mensagens nos dois sentidos. A tecnologia desenvolvida, no entanto, tem uma peculiari- dade: depois que um ramo de fibra ótica é utilizado para transportar matéria em uma direção, a fibra ótica guarda uma memória desse fato, e a partir de então esse ramo somente pode ser utilizado para transportar matéria naquela direção. Concentradores não são afetados por essa memória de direção.

O grupo de pesquisa da SBC é muito bom em física, mas muito fraco em computação. Por isso, você foi contratado para determinar se a rede de fibra ótica existente poderá ser utilizada pela SBC para transportar carga entre qualquer par de capitais, mesmo considerando a restrição de memória de sentido dos ramos de fibra ótica.

A primeira linha de cada caso de teste contém dois inteiros N e M separados por um espaço em branco, que representam, respectivamente, a quantidade de capitais (2 ≤ N ≤ 1.000) e a quantidade de ramos de fibra ótica existentes (1 ≤ M ≤ 50.000). As capitais são numeradas de 1 a N. Cada uma das M linhas seguintes de um caso de teste contém dois inteiros A e B (1 ≤ A, B ≤ N, A ≠ B) separados por um espaço em branco, indicando que existe um ramo de fibra ligando a capital A à capital B. Note que para comunicação de dados o ramo descrito pode ser utilizado para enviar mensagens tanto de A para B quanto de B para A, mas para transferência de matéria ele poderá ser utilizado em apenas uma direção. Há no máximo um único ramo de fibra ligando um par de capitais. O final da entrada é indicado por N = M = 0.

Para cada caso de teste da entrada seu programa deve imprimir uma única linha, contendo a letra ‘S’ caso seja possível utilizar a rede existente conforme especificado, ou a letra ‘N’ caso contrário.