XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: sapo.x, onde x deve ser c, cpp, java, js ou py

Sr. Sapo

O Sr. Sapo mora num lago de formato retangular dividido em um reticulado de células quadradas de um metro de lado. Algumas das células são pedras que estão acima do nível da água. O Sr. Sapo é muito atlético e pode saltar a distâncias de até três metros, mas curiosamente ele só pode saltar nas direções paralelas aos lados do lago. A figura (a) abaixo mostra um lago, e a figura (b) uma sequência de pulos do Sr. Sapo.

}
O Sr. Sapo está em uma pedra e quer ir visitar sua namorada que está em outra pedra. Ele está com pressa e não quer se molhar, portanto quer chegar ao seu destino pulando de pedra em pedra, sem cair na água. Dados o mapa do lago, a pedra em que o Sr. Sapo está e a pedra em que a sua namorada está, determine se é possível ele chegar ao seu destino sem se molhar.

Entrada

A primeira contém dois inteiros N, M, respectivamente a largura e o comprimento do lago em metros (ou seja, o lago é composto por N colunas e M linhas de células quadradas de 1m de lado). As colunas são numeradas de 1 a N e as linhas são numeradas de 1 a M. A segunda linha contém um inteiro P, o número de células que são pedras. Cada uma das P linhas seguintes contém dois inteiros C_{i e L_{i}, respectivamente o número da coluna e o número da linha de uma célula que é pedra. A linha seguinte descreve a célula em que o Sr. Sapo está e contém dois inteiros S_{C} e S_{L}, respectivamente a coluna e a linha da célula. A linha seguinte descreve a célula em que está a namorada do Sr. Sapo e contém dois inteiros R_{C} e R_{L}, respectivamente a coluna e a linha da célula.}

Saída

Seu programa deve produzir uma única linha na saída, contendo um único caractere, que deve ser `S' se for possível o Sr. Sapo chegar ao destino sem se molhar, ou `\texttt{N' caso contrário.}

Restrições

  • 3 ≤ N ≤ 100
  • 1 ≤ M ≤ 100
  • 2 ≤ P ≤ N\times M
  • 1 ≤ C_i ≤ M e 1 ≤ L_i ≤ M para 1 ≤ i ≤ P
  • 1 ≤ S_{C} ≤ N e 1 ≤ S_{L} ≤ M
  • 1 ≤ R_{C} ≤ N e 1 ≤ R_{L} ≤ M
  • As posições do Sr. Sapo e da sua namorada são distintas e ambas são posições de pedras especificadas na entrada.

Informações sobre a pontuação

  • Para um conjunto de casos de testes valendo 14 pontos, M = 1
  • Para um conjunto de casos de testes valendo outros 16 pontos, para a pedra em que o Sr. Sapo está inicialmente, há no máximo uma outra pedra para a qual ele pode saltar, e para todas as outras pedras, há no máximo duas para a qual ele pode saltar (ou seja, se o Sr. Sapo consegue chegar ao destino, há um único caminho de pedras que podem ser usadas, e esse caminho não tem "bifurcações").
  • Para um conjunto de casos de testes valendo outros 70 pontos, nenhuma restrição adicional.

Exemplos

Entrada 
4 5
6
1 1
2 2
1 4
3 4
3 5
4 5
1 1
4 5
Saída 
S

 

Entrada 
4 5
6
2 1
2 5
3 4
4 1
4 3
4 5
3 4
2 1
Saída 
N

 

Tarefas Programação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação