Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LUZES08 - Luzes de palco

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 ≤ 104) e o número de botões (1 ≤ B ≤ 106). As luzes são identificadas por números de 1 a L.

A segunda linha da entrada contém L inteiros Ii representando a configuração inicial das luzes (0 ≤ Ii ≤ 1 para 1 ≤ i ≤ L). Ii 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 Fi representando a configuração final das luzes (0 ≤ Fi ≤ 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


Adicionado por:Wanderley Guimarăes
Data:2012-07-17
Tempo limite:0.109s-1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Seletiva IOI 2008

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.