题意
给出一个 (N) 个点，(M) 条无向边的图 (G)，点的标号从 (1) 到 (N) ，边的标号从 (1) 到 (M) ，第 (i) 条边连接点 (a_i) 和 (b_i) 。 满足下列要求的图称为好图：
- 点 (1) 和点 (N) 不能相连
- 图中不存在自环和重边
两个人轮流向图中加无向边，保证初始的图一定是一个好图。当一方无法保证图为好图的前提下向图中加边时，为输。求出每场游戏的胜者是谁。
- All values in input are integers.
- (1≤T≤10^5)
- (2≤N≤10^5)
- (0≤M≤min(N(N−1)/2,10^5))
- (1≤a_i,b_i≤N)
- The given graph is a good graph.
- In one input file, the sum of (N) and that of (M) do not exceed (2×10^5).
题目链接：https://atcoder.jp/contests/arc105/tasks/arc105_e
分析
可以确定最后的图中一定包含两个联通块，一个是包含 (1) 的，一个是包含 (N) 的，假设二者的大小分别是 (n) 和 (N-n)。可以知道，能够添加的边的数量是 (frac{N(N-1)}{2}-n(N-n)-M)，该式为奇数时，先手胜；否则，后手胜。
- 当 (N) 是奇数时，(n) 和 (N-n) 中必然存在一奇一偶，即 (n(N-n)) 的结果是偶数，那么只要判断 (frac{N(N-1)}{2}-M) 的奇偶即可；
- 当 (N) 是偶数时，假设初始时刻， (1) 所在的联通块的大小为 (x) ，(N) 所在的联通块的大小为 (y) 。接下来对于 (frac{N(N-1)}{2}-xy-M) 中的 (x,y) 的奇偶进行讨论：
- 当 (x) 和 (y) 的奇偶性不同时，因为 (N) 为偶数，所以先手必然可以比后手多操作一次。那么，当 (frac{N(N-1)}{2}-M) 为奇数时，先手先操作，使得 (x,y) 变成偶数，然后不管后手怎么操作，先手都可以将它的操作抵消。当 (frac{N(N-1)}{2}-M) 为偶数时同理。所以，不管 (frac{N(N-1)}{2}-M) 是奇数还是偶数，先手都可以将局势向对自己有利的方向转化，故先手必胜；
- 当 (x) 和 (y) 的奇偶性相同时，无论先手和后手怎么操作， (frac{N(N-1)}{2}-xy-M) 的奇偶性都不会改变，故先手和后手的胜利取决于该式的初始值。
代码：
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N=1e5+5;
vector<int>pic[N];
bool vis[N];
int dfs(int u)
{
vis[u]=1;
int res=1;
for(int i=0;i<pic[u].size();i++)
{
int v=pic[u][i];
if(!vis[v])
res+=dfs(v);
}
return res;
}
int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
pic[i].clear();
for(int i=1;i<=n;i++) vis[i]=0;
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
pic[a].pb(b);
pic[b].pb(a);
}
if(n&1)
{
ll sum=1LL*n*(n-1)/2-m;
if(sum&1) printf("First
");
else printf("Second
");
}
else
{
int x=dfs(1);//cout<<"x="<<x<<endl;
int y=dfs(n);//cout<<"y="<<y<<endl;
if(x%2!=y%2) printf("First
");
else
{
ll sum=1LL*n*(n-1)/2-1LL*x*y-m;
if(sum&1) printf("First
");
else printf("Second
");
}
}
}
return 0;
}