A Dinastia dos Clubes Secretos

image imagem

A República de Xiangjião rege-se por leis e regras que não lembram a ninguém. Tem de se ser amigo de quem decide, e quem não é amigo, bem... amigo não é.

Décadas deste regime instituíram formas peculiares de se viver em sociedade. Por exemplo, se o João quiser fazer negócio com o Pedro, é bom que seja amigo dele de uma forma ou de outra ou então têm de se tornar amigos. Senão, não há negócio.

Amigo do meu amigo, meu amigo é. Logo, posso estar junto de uma pessoa sem saber que é minha amiga, porque esta amizade não é direta. Mas então, como é que se sabe?

Nesta república, popularizou-se o uso de cumprimentos secretos. Se João e Pedro se tornarem amigos, combinam um cumprimento secreto, o qual é um inteiro, que será usado pelos seus amigos também. Assim, formam-se clãs na República de Xiangjião e cada clã tem o seu cumprimento secreto único. Quando dois membros de clãs diferentes se tornam amigos, pelas circunstâncias da vida, os dois clãs juntam-se e, segundo as regras da república, adotam como cumprimento o maior dos dois cumprimentos. Os cidadãos desta república bananeira também se zangam com alguma facilidade e as consequências são duras: se dois membros de um clã se zangam, os ânimos exaltam-se tanto que todos quebram as amizades, ficando novamente isolados, sem amigos!

Afinal, há ou não há negócio? Esse é o seu desafio: determinar se os negócios são possíveis.

Tarefa

Faça um programa que processe uma sequência de ações e, para cada tentativa de negócio, escreva YES, se houver forma de negociar (porque os cidadãos são amigos), ou NO, se não houver forma de negociar (porque não são amigos). Por cada ação da forma "C $i$ ", o programa deverá indicar qual é o cumprimento do cidadão identificado por

i

Se houver $N$ cidadãos em Xiangjião, os cidadãos são identificados pelos inteiros de $0$ a $N - 1$ . Existem quatro tipos de ações, sendo $i$ e $j$ inteiros distintos que representam cidadãos:

A $i$ $j$ O cidadão $i$ (que não é amigo de $j$ ) torna-se amigo do cidadão $j$ ;

D $i$ $j$ O cidadão $i$ quer fazer negócio, vulgo Deal, com o cidadão $j$ ;

Z $i$ $j$ Os cidadãos $i$ e $j$ zangam-se; se forem amigos, desfazem-se todas as amizades do clã;

C $i$ O cidadão $i$ indica qual é o cumprimento secreto do seu clã.

No início, não há amizades feitas e cada cidadão tem o seu próprio identificador como cumprimento secreto, ou seja, o cumprimento do cidadão $0$ é $0$ , o cumprimento do cidadão $1$ é $1$ , etc. Assim, por exemplo, se o cidadão $3$ tem cumprimento $5$ (porque a vida o levou a ser amigo do cidadão $5$ ) e o cidadão $6$ tem cumprimento $7$ (por ser amigo de $7$ ), então, pela ação A 3 6, os cidadãos $3$ e $6$ tornam-se amigos e o cumprimento acordado será $7$ . Todos os amigos de $3$ e todos os amigos de $6$ usarão esse cumprimento, pois assim ditam as leis de Xiangjião.

Input

A primeira linha do input tem um inteiro

N

, que é o tamanho da população. A segunda linha tem um inteiro

K

, que é o número de ações da sequência. Cada uma das

K

linhas seguintes tem uma ação, no formato indicado acima para os quatro tipos possíveis.

Restrições

	$1 < N \leq 1 000$	Número de cidadãos da república
	$0 < K \leq 5 000$	Número de ações a processar

Output

Deverá haver uma linha no output por cada linha de pedido de negócio presente no input ou de pedido de cumprimento. Para pedidos de negócio, o conteúdo da linha será "YES" ou "NO", conforme haja ou não negócio. Para pedidos de cumprimento, a linha tem o inteiro correspondente.

Exemplo

Input

Output

NO
8
NO
YES
YES
YES
9
8

ToPAS'2025