赛时冲了两个多小时没冲出来，想得断断续续，导致没想到如何处理奇偶。
思路
根据限制条件一，可以知道最后的图一定是两个连通块，其中一块包含 \(1\)，另一块包含 \(n\)。因为此时再想连边就必须连通两个块，使其不合法了。
每次操作都是新增一条边，那么到最后的边数是多少呢？假设其中一个连通块有 \(k\) 个点，另一个则有 \(n-k\) 个点。两个连通块间肯定不会连边，因此这些没连的边就有 \(k(n-k)\) 条。如果没有限制，那么 \(n\) 个点之间就会互相连边，共有 \(\frac{n(n-1)}{2}\) 条边。再减去题目上已经给出的边，两个连通块内就一共会有会有 \(\frac{n(n-1)}{2} - m - k(n-k)\) 条边。
这时我们再来思考，先手获胜的条件是什么？谁不能操作就输了，因此先手想赢必须要刚好把需要放的边放完，也就是在上述式子值为奇时，先手获胜。观察发现，除了 \(k\) 是变量，其他条件我们都已知，也就是前面一部分的奇偶我们是知道的，因此根据后面的奇偶分讨即可。
以 \(n\) 的奇偶性分析。
-
\(n\) 为奇数时，若 \(k\) 为奇数，则 \(n-k\) 为偶数；若 \(k\) 为偶数，则 \(n-k\) 为奇数。因此，\(k(n-k)\) 一直都是偶数，与 \(k\) 无关了。只需看一下前面的式子是否是奇数，是则先手赢，否则后手赢。
-
\(n\) 为偶数时，\(k(n-k)\) 即可能是奇数，也可能是偶数，因此要继续判断。
-
当 \(1\) 号点所在连通块与 \(n\) 号点所在连通块奇偶性不相同时，又因为 \(n\) 为偶数，因此剩下的点个数一定是奇数个，也就是一定会有奇数个奇数连通块。先手可以根据自己的需求将一个奇数连到 \(1\) 号或 \(n\) 号，改变它的奇偶性，让两个块都变成自己需要的奇/偶。这样奇数块个数变成偶数，先手变为后手，于是现在的后手就可以“跟在”现在的先手后面，先手连哪个块后手就跟着连，两个奇数相加又变成偶数，对块的奇偶不产生影响。因此，先手必胜。
-
当 \(1\) 号点所在连通块与 \(n\) 号点所在连通块奇偶性相同时，不管是奇是偶，加起来都是偶数，因此剩下的块之和也为偶数。这就意味着剩下的块中会有偶数个个数为奇数
有点绕的块。若当前 \(1\) 号块的奇偶性已经和先手需要的奇偶性相同，那么先手就可以每次把余下的奇数块两两连接配成偶数块，如果后手想用奇数块搞事情把 \(1\) 号或 \(n\) 号块奇偶性打乱，那先手就跟一手将其变回来，跟不了了也没关系，还有另一个块供先手使用，因此先手必胜。
若不相同，那么后手采取此策略即可反制先手，让他失败。因此后手必胜。
至此，题目就做完了。代码好写，但是思维难度挺高，可以再仔细琢磨琢磨。
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,a[200005],b[200005];
int n,m,fa[200005];
ll sz[200005];
bool f;
int root(int x){
if(x==fa[x])return x;
return fa[x]=root(fa[x]);
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;//并查集求连通块大小
for(int i=1;i<=m;++i){
cin>>a[i]>>b[i];
int ra=root(a[i]),rb=root(b[i]);
if(ra!=rb){
sz[ra]+=sz[rb];
fa[rb]=ra;
}
}
int rn=root(n),r1=root(1);
if(rn==r1){//如果开局就不合法那么后手赢
cout<<"Second"<<endl;
return;
}
ll now=(ll)n*(ll)(n-1)/2-m;//式子的前一坨
if(n&1){//奇数只与now的奇偶有关
if(now&1)cout<<"First"<<endl;
else cout<<"Second"<<endl;
}
else{
if(now&1){
if(sz[r1]%2!=sz[rn]%2)cout<<"First"<<endl;//1，n两个连通块奇偶性不一样先手必胜
else{
if(sz[r1]&1)cout<<"Second"<<endl;//看先手需要的奇偶性
else cout<<"First"<<endl;
}
}
else{
if(sz[r1]%2!=sz[rn]%2)cout<<"First"<<endl;
else{
if(sz[r1]&1)cout<<"First"<<endl;
else cout<<"Second"<<endl;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--)solve();
return 0;
}