SPOJ Brasil

A cerimônia de premiação da OBI deste ano será espetacular. A atração principal será um show exclusivo dos Rolling Stones. Em preparação para o show, os técnicos de som e luzes da famosa banda estão visitando o Brasil. Um dos técnicos, ao saber que o evento tem tantos programadores altamente treinados, solicitou a ajuda para resolver um problema da banda.

Para controlar as luzes do palco durante o show, a banda tem um sofisticado equipamento com um painel coberto de botões. Cada botão controla duas luzes distintas: cada vez que o botão é pressionado o estado de ambas as luzes é invertido. Ou seja, se uma luz está apagada, após o botão ser pressionado ela se acende. Da mesma forma, se uma luz está acesa, após o botão ser pressionado ela se apaga. Dois botões distintos não controlam o mesmo par de lâmpadas.

O que o técnico quer saber é, dada uma certa configuração inicial do estado do conjunto de luzes, se existe uma sequência de acionamento dos botões para levar o estado das luzes para uma outra dada configuração.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha do conjunto de testes contém dois números inteiros L e B que indicam respectivamente o número de luzes (2 ≤ L ≤ 10⁴) e o número de botões (1 ≤ B ≤ 10⁶). As luzes são identificadas por números de 1 a L.

A segunda linha da entrada contém L inteiros I_i representando a configuração inicial das luzes (0 ≤ I_i ≤ 1 para 1 ≤ i ≤ L). I_i representa o estado da luz de número i: o valor ‘0’ indica que a luz está apagada e o valor ‘1’ indica que a luz está acesa. A terceira linha da entrada contém L inteiros F_i representando a configuração final das luzes (0 ≤ F_i ≤ 1 para 1 ≤ i ≤ L), de maneira similar à configuração inicial.

Cada uma das B linhas seguintes contém um par de inteiros X e Y que representam as luzes controladas por um dos botões (1 ≤ X, Y ≤ L).

Saída

Seu programa deve imprimir, na saída padrão, uma linha contendo a letra ‘S’ caso exista uma sequência de acionamento de botões que coloca as luzes na configuração final. Caso contrário, seu programa deve imprimir a letra ‘N’.

Exemplo

Entrada:
4 3
0 0 0 0
1 1 1 1
1 2
1 3
1 4

Saída:
S

Entrada:
4 2
1 0 1 0
1 1 0 0
1 2
3 4

Saída:
N