Zamjene


Submit solution


Points: 100 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Prolog, Python, Swift, VB

Dominik ha imaginado una serie de números enteros positivos p_1, ...,
p_n. Denotemos la versión ordenada de ese arreglo como q_1, ..., q_n.

Además, imaginó un conjunto de sustituciones permitidas. Si un par (X, Y) es un miembro del conjunto sustituciones permitidas, Dominik puede intercambiar los números en las posiciones de X y Y en el arreglo p.

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 A y B.

2- Agregar el par (A, B) 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 (A, B) vinculadas si el número de la posición A es posible transferir a la posición B utilizando solo las subtitulaciones permitidas. Llamemos al conjunto de todas las posiciones vinculadas para colocar A la nube de A. Una nube es buena si es posible para cada posición j de la nube lograr que p_j = q_j utilizando una serie de sustituciones permitidas.

Debes responder cuántos pares diferentes las posiciones (A, B) existen de tal manera que contiene:

  • Las posiciones A y B no están vinculadas una.

  • La nube de A no es buena y la nube de B no es buena

  • Si agregamos el par (A, B) al conjunto de sustituciones permitidas, la nube de A (uniéndola con la de B) se vuelve buena.

Tenga en cuenta: Los pares (A, B) y (B, A) se consideran un par idéntico.

Entrada

La primera línea de entrada contiene dos enteros N y Q (1 \le N, Q \le 100 000).

La segunda línea de entrada contiene N enteros p_1, ..., p_n (1 \le p_1, ..., p_n \le 100 000).

Cada una de las siguientes líneas Q contiene una consulta en el siguiente formato:

  • El primer número de la línea es el tipo de consulta T del conjunto {1, 2, 3, 4}.

  • A y B siguen (1 \le A, B \le N), si el tipo de consulta T es 1 o 2, dos números enteros diferentes Representan la sustitución (A, B).

Salida

Para cada consulta de tipo 3 o 4, envíe la respuesta en su línea separada. La respuesta a la consulta de tipo 3 es \("DA"\) (sí) o \("NE"\) (no), sin las comillas, y la respuesta a la consulta de tipo 4 es un número entero no negativo de la tarea.

Puntuación

En casos de prueba que valen 50\% del total de puntos, tendrá N, Q \le 1000.

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 1 porque el par de posiciones (2, 3) cumple con todos los requisitos dados. La respuesta a la segunda pregunta es NE (no) porque es imposible transferir los números 2 y 3 a las posiciones correspondientes, porque el conjunto de sustituciones permitidas está vacío.

Después de la tercera consulta, agregamos el par (2, 3) al conjunto de sustituciones permitidas. La respuesta a la cuarta consulta ahora es 0 porque 2 y 3 ya están vinculados, y la respuesta a la quinta La consulta es DA (sí), porque es posible ordenar el arreglo aplicando la sustitución permitida (2, 3).


Comments

There are no comments at the moment.