AtCoDeer y la permutación


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Authors:
Problem type
Allowed languages
C, C#, C++, Java, JS, Pascal, Python, VB

Tenemos una permutación p de N números enteros , p_1,p_2,\dots ,p_n . Dados M pares de números enteros entre 1 y N (incluidos), representados como ( x_1,y_1 ) , ( x_2,y_2 ) , \dots , ( x_m,y_m ). AtCoDeer el venado va a realizar la siguiente operación sobre p tantas veces como desee para que el número de i (1 \leq i \leq N) tal que p_i = i sea máximo:

  • Elegir j tal que (1 \leq j \leq M) , e intercambiar p_{x_j} con p_{y_j}

Encuentra el máximo posible de números i (1 \leq i \leq N) tal que p_i = i después de las operaciones .

Constantes

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • p es una permutación de enteros de 1 a N .
  • 1 \leq x_j,y_j \leq N
  • x_j \neq  y_j
  • Si i \neq j , {x_i,y_i} \neq {x_j,y_j}
  • Todos los valores de la entrada son enteros.

Entrada

  • La primera línea de entrada contiene a N y M.
  • La segunda línea de entrada contiene la permutacion p.
  • Las siguientes M líneas describen los pares de enteros.

Salida

Imprima el número máximo posible de números i tal que p_i = i después de las operaciones.

Ejemplo #1 de Entrada

5 2
5 3 1 4 2
1 3
5 4

Ejemplo #1 de Salida

2

Si realizamos una operación eligiendo j = 1 , p se convierte en [1,3,5,4,2] , lo cual es óptimo , la respuesta es 2.

Ejemplo #2 de Entrada

3 2 
3 2 1 
1 2 
2 3

Ejemplo #2 de Salida

3

Si realizamos las operaciones eligiendo j = 1 ,j = 2 ,j = 1 , en ese orden , p se convierte en [1,2,3] lo que obviamente es óptimo . Tenga en cuenta que es posible elegir el mismo par j cualquier número de veces.

Ejemplo #3 de Entrada

10 8
5 3 6 8 7 10 9 1 2 4
3 1
4 1
5 9
2 5
6 5
3 5
8 9
7 9

Ejemplo #3 de Salida

8

Ejemplo #4 de Entrada

5 1
1 2 3 4 5
1 5

Ejemplo #4 de Salida

5

No hay que hacer operaciones.


Comments

There are no comments at the moment.