← 返回题目列表

AtCoder · arc207_d

D. 吞噬者和蛋糕

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

一太郎和二郎二郎买了一个长方形的蛋糕作为送给母亲的礼物。 他们饿了,所以他们决定把蛋糕全部吃掉,只留下一块给妈妈。

有一个蛋糕,由排列成不同形状的碎片组成。 N 行和 M 列。 这件作品位于 i从顶部开始的第行和 j左边第 1 列有一个草莓,当 s_{i,j} is 1,并且没有草莓 0.

从一号太郎开始,两人交替对蛋糕进行操作,直到只剩下一块。 他们可以执行的操作如下。然而,它们无法执行吃掉所有剩余碎片的操作。

  • 吃掉从上往下第一行的所有棋子
  • 吃掉第一行从底部开始的所有棋子
  • 吃掉左边第一列的所有棋子
  • 吃掉右边第一列中的所有棋子

第一太郎想要留下一块有草莓的东西,第二郎想要留下一块没有草莓的东西。 确定当太郎操作得当时,无论二郎如何操作,一太郎是否都能留下一块草莓。

你被给予 T 测试用例;为他们每个人找到答案。

约束

  • 1 \le T \le 10^5
  • 1 \le N,M \le 10^{3}
  • 1<NM
  • s_{i} 是一个长度为 M 组成 0 和 1.
  • 总和 NM 所有测试用例最多 10^6.

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

N M
s_1
s_2
\vdots
s_N

输出

打印 T 行。

关于 i第行,用于 i- 第一个测试用例,打印 First 如果当太郎操作得当时,无论二郎如何操作,一号太郎都能留下一块草莓,并且 Second 否则。


示例输入 1

4
2 2
01
10
1 4
0100
4 1
0
1
0
0
5 5
00000
11100
01011
00100
01101

示例输出 1

Second
First
First
Second

对于第一个测试用例,无论太郎执行什么操作,二郎都可以留下一块没有草莓的东西。

对于第二个测试用例,如果太郎操作得当,无论二郎如何操作,他都可以留下一块草莓。

请注意,他们无法选择吃掉所有剩余棋子的操作。