Problem

5 /10


jugando con cuerdas

Theory Click to read/hide

Para resolver este problema, la teoría del análisis de juegos te será de gran ayuda: https://e-maxx.ru/algo/games_on_graphs

Problem

Dado un juego para dos jugadores con cuerdas.

Dado un conjunto formado por n cadenas no vacías. Durante el juego, dos jugadores construyen una palabra juntos, inicialmente esta palabra está vacía. Los jugadores se turnan. Durante su turno, el jugador debe agregar una letra al final de la palabra para que la palabra resultante sea un prefijo de al menos una línea del conjunto dado. El que no puede hacer un movimiento pierde.

Dado un conjunto de cadenas, determine quién será el ganador si ambos jugadores juegan de manera óptima.

Entrada:
La primera línea contiene el número entero n (1 ≤ n ≤ 105).
Cada una de las siguientes n líneas contiene una cadena no vacía del conjunto dado. La longitud total de todas las cadenas del conjunto no supera los 105. Todas las cadenas del conjunto se componen únicamente de letras latinas en minúsculas.

Salida:
Si el jugador que mueve primero gana, imprima "Primero", de lo contrario imprima "Segundo" (no es necesario imprimir comillas).

Ejemplos:
 
Entrada Salida
3
un
b
c
Primero
1
ab
Segundo