Zamjene
Dominik ha imaginado una serie de números enteros positivos . Denotemos la versión ordenada de ese arreglo como .
Además, imaginó un conjunto de sustituciones permitidas. Si un par es un miembro del conjunto sustituciones permitidas, Dominik puede intercambiar los números en las posiciones de y en el arreglo .
Marin le está dando a Dominik Q consultas, y cada una de ellas es de uno de los siguientes tipos:
1- Intercambiar números en posiciones y .
2- Agregar el par al conjunto de sustituciones permitidas. Marin puede dar un par que ya esté en el conjunto
3- ¿Diga si es posible ordenar la matriz usando solo las sustituciones permitidas? Las sustituciones se pueden utilizar en un orden arbitrario, y cada sustitución se puede realizado un número arbitrario de veces.
4- Llamemos a un par de posiciones vinculadas si el número de la posición es posible transferir a la posición utilizando solo las subtitulaciones permitidas. Llamemos al conjunto de todas las posiciones vinculadas para colocar la nube de . Una nube es buena si es posible para cada posición de la nube lograr que utilizando una serie de sustituciones permitidas.
Debes responder cuántos pares diferentes las posiciones existen de tal manera que contiene:
Las posiciones y no están vinculadas una.
La nube de no es buena y la nube de no es buena
Si agregamos el par al conjunto de sustituciones permitidas, la nube de (uniéndola con la de ) se vuelve buena.
Tenga en cuenta: Los pares y se consideran un par idéntico.
Entrada
La primera línea de entrada contiene dos enteros y .
La segunda línea de entrada contiene enteros .
Cada una de las siguientes líneas contiene una consulta en el siguiente formato:
El primer número de la línea es el tipo de consulta del conjunto .
y siguen , si el tipo de consulta es o , dos números enteros diferentes Representan la sustitución .
Salida
Para cada consulta de tipo o , envíe la respuesta en su línea separada. La respuesta a la consulta de tipo es \("DA"\) (sí) o \("NE"\) (no), sin las comillas, y la respuesta a la consulta de tipo es un número entero no negativo de la tarea.
Puntuación
En casos de prueba que valen del total de puntos, tendrá .
Ejemplos
Ejemplo de entrada 1
3 5
1 3 2
4
3
2 2 3
4
3
Ejemplo de salida 1
1
NE
0
DA
Ejemplo de entrada 2
5 5
4 2 1 4 4
3
4
1 1 3
3
4
Ejemplo de salida 2
NE
1
DA
0
Ejemplo de entrada 3
4 10
2 1 4 3
3
4
1 1 2
3
4
2 2 3
2 1 2
4
2 3 4
3
Ejemplo de salida 3
NE
2
NE
1
3
DA
Aclaración del primer caso de prueba:
La respuesta a la primera consulta es porque el par de posiciones cumple con todos los requisitos dados. La respuesta a la segunda pregunta es (no) porque es imposible transferir los números y a las posiciones correspondientes, porque el conjunto de sustituciones permitidas está vacío.
Después de la tercera consulta, agregamos el par al conjunto de sustituciones permitidas. La respuesta a la cuarta consulta ahora es porque y ya están vinculados, y la respuesta a la quinta La consulta es (sí), porque es posible ordenar el arreglo aplicando la sustitución permitida .
Comments