D: An Ordinary Game - AtCoder Regular Contest 064

配点 : 500 点

問題文

長さ 3 以上の文字列 s があります。 s の中に同一の文字が隣り合う箇所はありません。

高橋君と青木君がゲームで勝負します。二人は交互に次の操作を行います。高橋君が先手です。

s から両端以外の文字をひとつ取り除く。ただし、その文字を取り除くことで、s の中に同一の文字が隣り合う箇所ができる場合、その文字を取り除くことはできない。

先に操作を行えなくなった人が負けです。二人が最適に行動したとき、どちらが勝つかを判定してください。

制約

3 ≤ |s| ≤ 10^5
s は英小文字のみからなる。
s の中に同一の文字が隣り合う箇所はない。

入力

入力は以下の形式で標準入力から与えられる。

出力

先手の高橋君が勝つならば First を、後手の青木君が勝つならば Second を出力せよ。

入力例 1

aba

出力例 1

Second

先手の高橋君は操作を行うことができません。なぜならば、s から両端以外の文字の b を取り除くと、s は aa となって a が隣り合うからです。

入力例 2

abc

出力例 2

First

先手の高橋君が s から b を取り除くと、s は ac となります。すると、後手の青木君は操作を行うことができません。なぜならば、s には両端以外の文字が存在しないからです。

入力例 3

abcab

出力例 3

First

Score : 500 points

Problem Statement

There is a string s of length 3 or greater. No two neighboring characters in s are equal.

Takahashi and Aoki will play a game against each other. The two players alternately performs the following operation, Takahashi going first:

Remove one of the characters in s, excluding both ends. However, a character cannot be removed if removal of the character would result in two neighboring equal characters in s.

The player who becomes unable to perform the operation, loses the game. Determine which player will win when the two play optimally.

Constraints

3 ≤ |s| ≤ 10^5
s consists of lowercase English letters.
No two neighboring characters in s are equal.

Input

The input is given from Standard Input in the following format:

Output

If Takahashi will win, print First. If Aoki will win, print Second.

Sample Input 1

aba

Sample Output 1

Second

Takahashi, who goes first, cannot perform the operation, since removal of the b, which is the only character not at either ends of s, would result in s becoming aa, with two as neighboring.

Sample Input 2

abc

Sample Output 2

First

When Takahashi removes b from s, it becomes ac. Then, Aoki cannot perform the operation, since there is no character in s, excluding both ends.

Sample Input 3

abcab

Sample Output 3

First

AtCoder Regular Contest 064