Stalker

Felipe y su tripulación llegaron al ala de investigación en Patologías Psicológicas, una sección dedicada al estudio de los fenómenos mentales más extraños registrados por la humanidad durante los últimos tres siglos.

Mientras Franklin discutía con unos robots archivistas sobre la clasificación correcta de las neurosis interplanetarias e Isabel revisaba algunos estudios científicos, Charly comenzó a curiosear entre los expedientes históricos almacenados en enormes anaqueles automáticos.

Los casos estaban organizados cronológicamente y documentaban todo tipo de comportamientos extraños observados desde finales del siglo XXI hasta la actualidad. Muchos de ellos tenían algo en común: las antiguas redes sociales.

Charly siempre había escuchado historias sobre ellas. Antes de ser abolidas por los gobiernos terrestres, las redes sociales habían sido una de las formas más populares de comunicación humana. Sin embargo, también habían provocado innumerables controversias, conflictos y comportamientos difíciles de explicar.

—No puedo creer que la gente hiciera estas cosas —dijo mientras hojeaba algunos expedientes.

—La psicología humana es compleja —respondió Isabel sin levantar la vista de sus notas.

—Compleja es una palabra elegante para decir que estaban completamente locos.

Charly continuó revisando archivos cada vez más extraños. Había casos de personas que viajaban entre sistemas solares para tomar fotografías de su desayuno, individuos que discutían durante años sobre temas irrelevantes y comunidades enteras dedicadas a competir por quién podía realizar la acción más absurda imaginable.

Finalmente encontró un expediente particularmente llamativo.

El archivo estaba marcado con sellos de advertencia y varias anotaciones de los investigadores de MANDRÁGORA-88b.

En la portada podía leerse:

CASO #██████

Y el primer reporte decía algo así:

Después de meses de entrenamiento con los mejores stalkers de San Luis Potosí, Camila finalmente logró cumplir su sueño: convertirse en una experta certificada por la OPI (Organización de Persecución en Internet), una prestigiosa organización dedicada al análisis avanzado de datos en internet.

Mientras una persona común revisa una historia de Instagram una o dos veces, Camila es capaz de recordar exactamente quién apareció en la lista de vistas, en qué posición apareció y cómo cambió la lista durante el día. Debido a esta extraña habilidad, sus compañeros de la OPI comenzaron a sospechar que estaba dedicando demasiado tiempo al entrenamiento.

Para demostrar que sus capacidades son las mejores, Camila les propuso un desafío. Mostró algunas observaciones realizadas en distintos momentos del día y les pidió determinar la mínima cantidad de visualizaciones de una historia que pudieron haber ocurrido para que dichas observaciones fueran posibles. Si una misma persona vió la historia varias veces, cada visualización cuenta por separado.

Antes de comenzar, Camila les compartió un dato que todo miembro de la OPI aprende durante su primer día de entrenamiento: La lista de vistas de una historia se encuentra ordenada de la persona que la vio más recientemente a la que la vio hace más tiempo. Cada vez que una persona ve la historia ocurre exactamente una de las siguientes situaciones:

• Si su perfil ya se encontraba en la lista, este se mueve al primer lugar.
• Si su perfil no se encontraba en la lista, aparece en el primer lugar.

Se te dan \(T\) momentos observados por Camila. En el momento \(i\) se conoce la lista \(A_i\) de perfiles que habían visto la historia hasta ese instante, ordenada de más reciente a más antiguo.

Además, como Camila es una profesional certificada por la OPI y no una aficionada, se garantiza que las observaciones son consistentes: si un perfil aparece por primera vez en algún momento, entonces seguirá apareciendo en todos los momentos posteriores.

Se te harán consultas de la forma \((l, r)\). Para una consulta, debes asumir que el momento \(l\) es el primer instante observado. Tu tarea consiste en determinar la mínima cantidad de visualizaciones necesarias para construir la lista \(A_l\) y, posteriormente, obtener exactamente las listas observadas por Camila en los momentos \(l + 1, l + 2, \dots, r\) (en ese orden).

Fig 1. Celular de Franz

Entrada

La primera línea contiene dos enteros \(T\) y \(Q\), la cantidad de momentos observados y la cantidad de consultas.

Después siguen \(T\) bloques. El bloque \(i\) está formado por dos líneas. La primera contiene un entero \(N_i\), la cantidad de perfiles en la lista observada. La segunda contiene \(N_i\) cadenas distintas que representan la lista \(A_i\), ordenada de la persona que vio la historia más recientemente a la que la vio hace más tiempo.

Finalmente, siguen \(Q\) líneas. Cada una contiene dos enteros \(l\) y \(r\), que describen una consulta.

Salida

Para cada consulta imprime una línea con la respuesta correspondiente.

Ejemplos

Ejemplo 1

Entrada

2 1
3
anabanana camila sofia
3
camila anabanana sofia
1 2

Salida

4

Para formar la primera lista se necesitan al menos \(3\) visualizaciones. Después, basta con que camila vuelva a ver la historia para obtener la segunda lista. Por lo tanto, la respuesta es \(4\).

Ejemplo 2

Entrada

3 2
2
sofia camila
3
anabanana sofia camila
3
camila anabanana sofia
1 3
2 3

Salida

4
4

Ejemplo 3

Entrada

4 3
5
daniel sofia lemus cubone pibble
5
lemus daniel sofia cubone pibble
6
camila lemus daniel sofia cubone pibble
6
daniel camila lemus sofia cubone pibble
1 4
2 4
3 4

Salida

8
7
7

Ejemplo 4

Entrada

5 4
6
a b c d e f
7
x a b c d e f
8
y x a b c d e f
9
b z y x a c d e f
10
w b z y x a c d e f
1 5
2 5
3 4
4 5

Salida

11
11
10
10

Límites

• \(1 \le T,Q \le 5 \cdot 10^5\)
• \(1 \le N_i\)
• \(\sum N_i \le 5 \cdot 10^5\)
• Cada perfil aparece a lo más una vez dentro de una misma lista.
• Cada cadena tiene longitud entre 1 y 20.
• Los nombres de perfil contienen únicamente letras minúsculas del alfabeto inglés.
• \(1 \le l \le r \le T\)

Detalles de Implementación

• Si un perfil aparece en el momento \(i\), entonces también aparecerá en todos los momentos posteriores.
• Las listas proporcionadas siempre son consistentes con las reglas descritas en el enunciado.
• Una misma persona puede visualizar la historia varias veces; cada visualización cuenta por separado.

Subtareas

• Subtarea 1 [5 puntos]: Todas las consultas cumplen que \(l = r\).
• Subtarea 2 [10 puntos]: La cantidad \(N_i\) es fija para todo \(i\), y \(N_i \leq 3\).
• Subtarea 3 [15 puntos]: La cantidad \(N_i\) es fija para todo \(i\), y ocurren a lo más \(2\) visualizaciones entre momentos consecutivos.
• Subtarea 4 [35 puntos]: \(T, Q \leq 100\) y \(\sum N_i \le 1000\).
• Subtarea 5 [35 puntos]: Sin restricciones adicionales.