カードの表裏に書かれた数字を頂点として，カードを辺とみなしたグラフを考える．
カードの表裏を選ぶ事は，辺に向きを付けることとみなす． 連結成分毎に考えればよい． 連結成分をtreeの場合を先に解いて，そうで無い場合はtree に帰着させる．
連結成分 を固定し，頂点の個数を
個とする．
(i) がtreeのとき
根を一つ任意にとる．DFSをして，親から子に向かって辺に向きをつければ， 根以外の頂点 個をすべて選べる． また，辺が
個なので，
に対してはこれが最大．
(ii) がtreeでないとき
全域木 をとることで treeに帰着させたい． 全域木以外に1つ以上辺 があるので，これを追加すると サイクルが出来る．
を根して全域木に対してDFSをすれば，(i)より
個選べる．また，
の向きを
ととれば，
も選べる． よって，
個すべて選べるので，
に対してはこれが最大．
長さ2,1,のサイクルが存在する場合に注意． 今回は，下の実装でも求まる． 無向グラフであることを使って，長さ2のサイクルを正しく求めている．
安全に行くなら，サイクル検出と連結成分の長さを求めるのを別々に行う．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m;
cin >> m;
n = 4e5+10;
vvll to(n);
rep(i,m){
ll a,b; cin >> a >> b;
--a,--b;
to[a].push_back(b);
to[b].push_back(a);
}
bool cyc = false;
ll cnt = 0;
vll vis(n);
if(vis[cu]) { cyc = true; return; }
vis[cu] = true;
cnt++;
f(f, ne, cu);
}
};
ll ans = 0;
rep(i,n) if(!vis[i]){
cyc = false;
cnt = 0;
dfs(dfs, i);
ans += cnt - !cyc;
}
cout << ans << endl;
return 0;
}
