好题。
如果 \(1\) 和 \(n\) 一直联通，开始即结束。
如果 \(n\mod 4=1\)，那么 \(\frac 12x(x+1)+\frac12(n-x)(n-x+1)\) 为偶数。
如果 \(n\mod 4=3\)，那么 \(\frac 12x(x+1)+\frac12(n-x)(n-x+1)\) 为奇数。
这两种情况最后连的边的数量奇偶固定，结合 \(m\) 的大小可以算出答案。
后面 \(n\mod 4=2\) 和 \(n\mod 4=0\) 的情况是类似的，以 \(n\mod4=2\) 为例。
如果 \(m\) 为奇数，先手目标为让最后两个连通大小为奇数，后手要让最后两个连通块大小为偶数。那么当且仅当一开始 \(1\) 所在连通块大小和 \(n\) 所在连通块大小都是偶数，后手能必胜。
如果 \(m\) 为偶数，先手目标为让最后两个连通大小为偶数，后手要让最后两个连通块大小为奇数。那么当且仅当一开始 \(1\) 所在连通块大小和 \(n\) 所在连通块大小都是奇数，后手能必胜。
// LUOGU_RID: 135034621
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n,m,fa[N],sz[N];
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
int main()
{
// freopen("deadlock.in","r",stdin);
// freopen("deadlock.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
int c=0;
for(int i=1;i<=n;i++)
fa[i]=i,sz[i]=1;
for(int i=1,u,v;i<=m;i++)
{
scanf("%d%d",&u,&v);
if(find(u)^find(v))
{
sz[find(v)]+=sz[find(u)];
fa[find(u)]=find(v);
}
}
if(find(1)==find(n))
{
puts("Second");
continue;
}
if(n%4==1)
{
if(m&1)
puts("First");
else
puts("Second");
continue;
}
if(n%4==3)
{
if(m&1)
puts("Second");
else
puts("First");
continue;
}
if(n%4==0)
{
if(m&1)
{
if(sz[find(1)]%2==1&&sz[find(n)]%2==1)
puts("Second");
else
puts("First");
}
else
{
if(sz[find(1)]%2==0&&sz[find(n)]%2==0)
puts("Second");
else
puts("First");
}
continue;
}
if(m&1)
{
// printf("odd:%d %d ",sz[find(1)]&1,sz[find(n)]&1);
if(sz[find(1)]%2==0&&sz[find(n)]%2==0)
puts("Second");
else
puts("First");
}
else
{
// printf("even:%d %d ",sz[find(1)]&1,sz[find(n)]&1);
if(sz[find(1)]%2==1&&sz[find(n)]%2==1)
puts("Second");
else
puts("First");
}
}
}