Convención P75322

Este año, Walker no podrá asistir a la convención nacional de rangers. Por eso le pide a Trivette que vaya en su lugar. Cuando Trivette llega al lugar se da cuenta de que no conoce a nadie. Como que a él le gustaría conocer a los presentes, va a tener que presentarse a todos ellos, uno por uno. Por ejemplo, para conocer a “Roger”, puede ir y decirle “Hola Roger, permíteme que me presente, soy Trivette.”. Pero presentarse directamente a un desconocido resulta un poco embarazoso. Por ello, una vez conoce a una persona, puede pedirle a ésta que le presente a sus conocidos, lo cual resulta más fácil. Por ejemplo, si “Roger” conoce a “Sullivan”, puede decirle a “Roger” lo siguiente: “Roger, podrías presentarme a Sullivan?”. Si luego “Sullivan” conoce a “Jack”, podrá pedirle “Sullivan, podrías presentarme a Jack?”. Con ello, Trivette habría conocido a tres personas usado una única auto- presentación.

Debes escribir un programa que, dada la lista de personas presentes, y la relación de conocimiento mútuo entre ellas, sea capaz de calcular el mínimo número de auto-presentaciones que necesitará Trivette para acabar conociendo a todo el mundo.

Entrada

La entrada tiene, en una primera línea, un número entero n que cumple 1≤ n≤ 10⁵, que representa el número total de personas. Después vienen n líneas, con un nombre en cada una de ellas, que representa el conjunto de personas presentes, y donde cada nombre se constituye de como mucho 10 letras mayúsculas y minúsculas. En una nueva línea hay un número entero m que cumple 1≤ m≤ 50000, que representa el número de relaciones de conocimiento mútuo. Después vienen m líneas, con dos nombres X e Y en una línea, para indicar que X e Y se conocen. La pareja X Y únicamente aparece una vez en la entrada (bien sea X Y, o bien Y X). Nunca aparecerán auto-relaciones de amistad (X X).

Salida

Escribe una línea con el mínimo número de auto-presentaciones que necesitará Trivette para acabar conociendo a todas las personas.

Puntuación

• TestA:  ‍ Entradas con NUM que cumplan 1≤ n,m≤ 4.  ‍25 Puntos ‍

• TestB:  ‍ Entradas con NUM que cumplan 1≤ n,m≤ 100.  ‍25 Puntos ‍

• TestC:  ‍ Entradas con NUM que cumplan 1≤ n,m≤ 2000.  ‍25 Puntos ‍

• TestD:  ‍ Entradas con NUM que cumplan 1≤ n,m≤ 50000.  ‍25 Puntos ‍