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.|

FUSOES1 - Fusões

A informatização dos sistemas bancários permitiu grandes economias de tempo e dinheiro, permitindo que vários tipos de transações financeiras pudessem ser realizadas pela Internet. Para possibilitar isso, cada banco recebeu um código bancário, que é um número utilizado pelos sistemas de computador para identificar cada banco.

Quando um banco decide comprar outro, ocorre o que se chama uma fusão: os dois bancos tornam-se um só banco. Para manter compatibilidade com os sistemas eletrônicos dos bancos, qualquer um dos códigos dos antigos bancos pode ser usado para se referir ao novo banco.

Com a crise econômica internacional, as fusões entre bancos têm sido cada vez mais comuns; por isso, muitas vezes é difícil decidir se dois códigos bancários na realidade se referem ao mesmo banco (devido aos dois bancos terem se fundido, diretamente ou não).

Tarefa

Escreva um programa que, dada uma série de fusões entre bancos, responde a várias consultas perguntando se dois códigos bancários se referem ao mesmo banco.

Entrada

A primeira linha da entrada contém dois inteiros N e K, indicando o número de bancos e o número de operações efetuadas (1 ≤ N ≤ 100.000, 1 ≤ K ≤ 100.000). Os códigos de cada um dos N bancos, inicialmente, são os inteiros de 1 até N.

Cada uma das K linhas seguintes descreve ou uma fusão entre bancos ou uma consulta.

  • Uma fusão é descrita na entrada como uma linha que começa com o caractere 'F', um espaço, e dois códigos bancários, que se referem aos dois bancos que estão sofrendo a fusão, separados por um espaço em branco;
  • Uma consulta é descrita na entrada como uma linha que começa com o caractere 'C', um espaço, e os dois códigos a serem consultados, separados por um espaço em branco. Os códigos bancários consultados são sempre distintos.

As fusões são sempre realizadas entre bancos diferentes, e todos os códigos bancários fornecidos na entrada são válidos.

Saída

Seu programa deve imprimir uma linha para cada consulta na entrada. Caso os dois códigos bancários consultados se refiram ao mesmo banco, imprima uma linha contendo o caractere 'S'; caso contrário, imprima uma linha contendo apenas o caractere 'N'.

Exemplo

Entrada
3 5
C 1 2
F 1 2
C 1 2
F 1 3
C 1 3

Saída
N
S
S

Entrada
4 5
F 1 2
F 2 3
C 1 3
F 2 4
C 1 4

Saída
S
S

Entrada
4 4
F 1 2
F 3 4
F 1 3
C 2 4

Saída
S

Adicionado por:Wanderley Guimarăes
Data:2011-04-10
Tempo limite:0.191s
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:OBI 2010 - fase 2 nível 1

hide comments
2013-03-17 18:03:13 Thalyson Nepomuceno [UECE]
Siqueira, isso é um problema clássico sobre Union-Find, só aplicar o algoritmo que passa...
2011-10-15 23:22:54 Siqueira Júnior
ou entăo alguma idéia que estăo usando.
2011-10-15 23:21:38 Siqueira Júnior
alguem bota mais exemplos de casos certos?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.