CF455B- A Lot of Games（Trie樹+DFS+博弈）

time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Andrew, Fedor and Alex are inventive guys. Now they invent the game with strings for two players.

Given a group of n non-empty strings. During the game two players build the word together, initially the word is empty. The players move in turns. On his step player must add a single letter in the end of the word, the resulting word must be prefix of at least one string from the group. A player loses if he cannot move.

Andrew and Alex decided to play this game k times. The player who is the loser of the i-th game makes the first move in the (i + 1)-th game. Guys decided that the winner of all games is the player who wins the last (k-th) game. Andrew and Alex already started the game. Fedor wants to know who wins the game if both players will play optimally. Help him.

Input

The first line contains two integers, n and k (1 ≤ n ≤ 105; 1 ≤ k ≤ 109).

Each of the next n lines contains a single non-empty string from the given group. The total length of all strings from the group doesn't exceed 105. Each string of the group consists only of lowercase English letters.

Output

If the player who moves first wins, print "First", otherwise print "Second" (without the quotes).

Sample test(s) input

2 3
a
b
      

output

First
      

input

3 1
a
b
c
      

output

First
      

input

1 2
ab
      

output

Second      

題意：有n個字元串，k次遊戲，每次遊戲先手先在空字元串上加上一個字母，後手在加，且要保證字元串都要是n個字元串的字首。上一盤輸的人下一盤會變成先手，問最後誰赢？      

思路：先建立Trie樹，考慮3中情況：1、後手能必勝：那麼後手可以保證一直是後手，且一直赢，那麼勝者就是後手。 2、先手能必勝，且能必輸：那麼先手可以保證一直輸，然後在最後一盤的時候選擇必勝。 3、先手能必勝，但不不能必輸：那麼每次先手隻能勝，而且每次比賽先手後手會調換位置，是以隻要看K的奇偶性就行。      

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 100000+10;
int sz;
int trie[maxn][26];
int n,k;
int getIdx(char a){
    return a-'a';
}
void insert(string st){
    int u = 0;
    for(int i = 0; i < st.size(); i++){
        int k = getIdx(st[i]);
        if(!trie[u][k]){
            trie[u][k] = sz;
            memset(trie[sz],0,sizeof trie[sz]);
            sz++;
        }
        u = trie[u][k];
    }
}
void init(){
    sz = 1;
    memset(trie[0],0,sizeof trie[0]);
}

bool dfs1(int id){
    for(int i = 0; i < 26; i++){
        if(trie[id][i]!=0){
            if(!dfs1(trie[id][i])){
                return 1;
            }
        }
    }
    return 0;
}
bool dfs2(int id){
    int ans = 0,flag = 1;
    for(int i = 0; i < 26; i++){
        if(trie[id][i] != 0){
            flag = 0;
            if(!dfs2(trie[id][i]))
                return 1;
        }
    }
    if(flag) return 1;
    return 0;
}

int main(){

    while(~scanf("%d%d",&n,&k)){
        string tstr;
        init();
        for(int i = 0; i < n; i++){
            cin >> tstr;
            insert(tstr);
        }
        int a = dfs1(0),b = dfs2(0);
        if(a==0){
            printf("Second\n");
        }
        else if(a==1&&b==1){
            printf("First\n");
        }
        else if(a==1&&b==0){
            if(k&1){
                printf("First\n");
            }else{
                printf("Second\n");
            }
        }
    }
    return 0;
}