# 455B

## Tutorial

Trie can be implemented with a two dimentional array.

## Solution

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

#define D(x) x

const int MAX_CHAR_NUM = 30;
const int MAX_N = int(1e5) + 10;
const int MAX_NODE_NUM = MAX_N;

int trie[MAX_NODE_NUM][MAX_CHAR_NUM];
int node_num;

int n, round_num;
char st[MAX_N];
bool leaf;

void trie_init()
{
memset(trie, -1, sizeof(trie));
node_num = 1;
}

int convert(char ch)
{
return ch - 'a';
}

void add(char* st)
{
int u = 0;
for (int i = 0; st[i]; i++)
{
int index = convert(st[i]);
if (trie[u][index] == -1)
{
trie[u][index] = node_num++;
}
u = trie[u][index];
}
}

void input()
{
scanf("%d%d", &n, &round_num);
for (int i = 0; i < n; i++)
{
scanf("%s", st);
add(st);
}
}

bool dfs(int u)
{
bool have_child = false;
bool ret = false;
for (int i = 0; i < 26; i++)
{
if (trie[u][i] != -1)
{
have_child = true;
ret = ret || !dfs(trie[u][i]);
}
}
if (have_child)
return ret;
return leaf;
}

void output()
{
for (int i = 0; i < 24; i++)
{
for (int j = 0; j < 26; j++)
{
printf("%d ", trie[i][j]);
}
puts("");
}
}

int main()
{
trie_init();
input();
leaf = false;
bool win = dfs(0);
leaf = true;
bool lose = dfs(0);
if (win && lose)
{
puts("First");
}else if (win && !lose)
{
if (round_num & 1)
puts("First");
else
puts("Second");
}else if (!win)
{
puts("Second");
}
return 0;
}