Rodobaldo Martínez es el alcalde de una gran ciudad. En su ciudad hay grandes aeropuertos, granjas, industrias monopólicas de producción de leche y otros derivados de las rubinos, pero este problema no es sobre rubinos, o quizás si, quien sabe! Rodobaldo Martínez en su ciudad tiene un club de fútbol. En la primera parte de la temporada parecía que podían tener una temporada decente pero como a "muchos" equipos famosos se le vino a pique en una semana. En su club todos los jugadores son seguidores del FC Barcelona o del Real Madrid CF.

En un principio, quiso que jugaran separados, como en dos divisiones pero entonces dejo jugar a los albinos, con resultados inmediatos. Su club, que se llama obviamente RM FC, esta en un apuro, obviamente causado por las grandes ideas(como poner a jugar futbol a las rubinos o incluso a los madridistas) que se le ocurren a las grandes rubinos que viven en esa ciudad, como RM.

Ahora vamos para el problema. En el club hay muchas amistades, incluso amistades con distintas afiliaciones futbolísticas y formas de ver la vida. Las amistades forman grupos de amigos. Un grupo de amigos es un conjunto de jugadores tal que a través de una relación de amistades se puede ir entre cualquier par. Algo asi: si María y Alfie son amigas y Kathy y María son amigas entonces las tres forman un grupo de amigos. El valor de un grupo de amigos es ~X~, donde:

~X = (B-R) * (B-R)~

~B~ - cantidad de seguidores del FC Barcelona

~R~ - cantidad de seguidores del RM CF

El valor del club es la suma de los valores de los grupos de amigos. Rodobaldo quiere "mejorar" el club y para eso el puede pagarle a un par de sus jugadores una botella de ron y bajo los efectos del alcohol se hagan los mejores amigos del mundo, por lo tanto el va a crear la cantidad de amistades necesarias, digamos ~k~, para que en su club haya un grupo de amigos, es decir todos unidos. El quiere saber cual es mayor valor del club que puede tener luego de crear ~0,1,2 ... k~ amistades convenientemente.

Entrada

En la primera linea aparecerá ~N~ y ~M~, la cantidad de jugadores del club y la cantidad de amistades que inicialmente hay. La segunda linea contiene una cadena de caracteres, digamos s, de tamaño ~N~, donde el ~i-esimo~ carácter puede ser una ~'B'~ o una ~'R'~, representando la afiliación futbolística del ~i-esimo~ jugador. Las siguientes ~M~ lineas contienen ~U_i~ y ~V_i~ representando que existe una amistad entre los jugadores ~U_i~ y ~V_i~.

Salida

~k+1~ lineas, en la linea ~i-esima~ el mayor valor del club que puede tener luego de crear ~i-1~ amistades.

Ejemplo entrada

7 5
BRRRBBB
1 2
1 3
2 3
4 6
7 4

Ejemplo salida

3
5
1

Explicación

Tenemos los grupos de amigos:{1,2,3},{4,6,7},{5}

1-Si no creamos ninguna amistad el valor de club es ~3(X({1,2,3}) = 1, X({4,6,7}) = 1, X({5})=1)~

2-Podemos crear la amistad (4,5) y el valor del club es ~5(X({1,2,3}) = 1, X({4,6,7,5}) = 4)~

3-Podemos crear las amistades ~(1,4)~ y ~(5,6)~ y el valor del club es ~1(X({1,2,3,4,6,7,5}) = 1)~

Limites

· ~1 \le U_i, V_i \le N~

· ~0 \le M \le (N *(N-1)) / 2~

· Subtarea 1. ~N = 10~ ~25~ puntos.

· Subtarea 2. ~N = 1000~ ~75~ puntos.