构建trie树，可以得到4类结点：必胜点，必负点，完全主宰点（可胜可负），完全无法主宰点（无法控制最终胜负）。递归到叶子结点，即为必胜点，回溯分情况讨论。注意叶子结点使用属性n来控制，n表示当前结点的儿子结点的数目，叶子结点没有儿子。
/* 456D */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
using namespace std; typedef struct trie_t {
int n;
int next[];
trie_t() {
n = ;
memset(next, , sizeof(next));
}
} trie_t; const int maxn = 1e5+; trie_t T[maxn];
int L = ;
char s[maxn];
int n, m; int newTrie() {
return ++L;
} void create(char *s, int rt) {
int p = rt;
int i = , id; while (s[i]) {
id = s[i] - 'a';
if (T[p].next[id] == ) {
T[p].next[id] = ++L;
++T[p].n;
}
p = T[p].next[id];
++i;
}
} int dfs(int rt) {
int i;
int st = ; if (T[rt].n == )
return ; for (i=; i<; ++i) {
if (T[rt].next[i])
st |= dfs(T[rt].next[i]);
}
switch(st) {
case :
return ;
case :
return ;
case :
return ;
case :
return ;
default:
return ;
}
} int main() {
int i, j, k; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif scanf("%d %d", &n, &m);
// build trie
for (i=; i<n; ++i) {
scanf("%s", s);
create(s, );
}
// get the key point
int st = ;
for (i=; i<; ++i) {
if (T[].next[i])
st |= dfs(T[].next[i]);
} if (st == ) {
puts("First");
return ;
} else if (st == ) {
puts("Second");
return ;
}
if (st == ) {
puts("Second");
return ;
}
if (m & ) {
puts("First");
} else {
puts("Second");
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}