このゲームは，Shannon Switching Game の Graphic Matroid を Binary Matroid に変更したものです．
このゲームの必勝法を理解するには，まずは元々の Shannon Switching Game の必勝法を理解するのが良いでしょう．

Shannon Switching Game

Shannon Switching Game は以下のようなゲームです．

無向グラフ \(G = (V, E)\) と \(2\) 頂点 \(u, v \in V\) が与えられる． Alice と Bob は交互に以下の操作を行う．

• Alice: 辺 \((x, y) \in E\) を \(1\) つ選び，頂点 \(x\) と頂点 \(y\) を縮約 (くっつけて 1 つの頂点に) する．
• Bob: 辺 \((x, y) \in E\) を \(1\) つ選び，削除する．

頂点 \(u\) と頂点 \(v\) がくっついたら Alice の勝ち，頂点 \(u\) と頂点 \(v\) が非連結になったら Bob の勝ちである．

Alice が先手であるとき，辺 \((u, v)\) を \(E\) に追加することで，Bob が先手である場合に帰着することができます．(Bob は初手で辺 \((u, v)\) を削除するしかない)
Bob が先手であるとき，このゲームの勝敗は以下のように判定することができます．

1. Alice は，\(u\) でも \(v\) でもない不要な頂点 (と，それに繋がる辺) を好きなだけ削除する．
2. その後，\(E\) から辺素な \(2\) つの全域木 \(T_1, T_2\) を取ることができれば Alice の勝ち，そうでなければ Bob の勝ちである．

ある \(u, v\) を含む頂点集合 \(U \subseteq V\) が存在し，辺素な \(2\) つの木 \((U, T_1), (U, T_2)\) が存在 \(\implies\) Alice 勝ち

\(E = T_1 \cup T_2\) であるとして良いです．(Alice が不利になりますが，この状態で Alice が勝てることを示します．)
Bob が辺 \((a, b) \in T_1\) を削除したとき，\(T_1\) は \(a\) を含む連結成分と，\(b\) を含む連結成分の \(2\) つに分解されます．\(T_2\) には，この \(2\) つの連結成分間を結ぶ辺が \(1\) 本以上存在するので，Alice はそのうち \(1\) つを選び，縮約を行えば良いです．これにより，\(T_1\) は木に戻り，「辺素な \(2\) つの木 \(T_1, T_2\) が存在」を満たしたまま頂点数を減らすことができます．

任意の \(u, v\) を含む頂点集合 \(U \subseteq V\) に対し，辺素な \(2\) つの木 \((U, T_1), (U, T_2)\) が存在しない \(\implies\) Bob 勝ち

辺素な \(2\) つの木 \((U, T_1), (U, T_2)\) を取ることができる，極大な頂点集合 \(U\) を集めたものを \(\mathcal U\) とします．各 \(U \in \mathcal U\) に対し，\(u \in U\) かつ \(v \in U\) とはならないことに注意します．
ここで，異なる \(2\) つの \(U_1, U_2 \in \mathcal U\) に対し，\(U_1 \cap U_2 = \emptyset\) が成り立ちます．
(\(U_1 \cap U_2 \ne \emptyset\) なる \(2\) つの集合 \(U_1, U_2\) が条件を満たすなら，\(U_1 \cup U_2\) も条件を満たすため (証明: \(U_1\) の辺素な \(2\) つの木に対し，「\(U_1\) を \(1\) つの頂点に縮約したときの \(U_2\) の辺素な \(2\) つの木」を加えれば良い) )

Bob は，各 \(U \in \mathcal U\) を \(1\) つの頂点へ縮約してしまって良いです．(Bob が不利になりますが，この状態で Bob が勝てることを示します．)
このとき，グラフは以下のようになります．

• \(2\) つの頂点 \(u, v \in V\) が存在し，くっついていない．
• \(|U| ≥ 2\) なる任意の頂点集合 \(U \subseteq V\) に対し，辺素な \(2\) つの木 \((U, T_1), (U, T_2)\) が存在しない

このとき，「\(|U| ≥ 2\) なる任意の頂点集合 \(U \subseteq V\) に対し，\(U\) 内の辺の本数 \(E(U)\) は \(2|U| - 3\) 以下」が成り立ちます． (これを満たさない極小な \(U\) を取ると，Nash–Williams の定理 より，\(U\) を頂点とする辺素な \(2\) つの木が取れる)

さて，辺集合 \(E\) に辺 \((u, v)\) を追加すると，「\(|U| ≥ 2\) なる任意の頂点集合 \(U \subseteq V\) に対し，\(U\) 内の辺の本数 \(E(U)\) は \(2|U| - 2\) 以下」となるので，Nash–Williams の定理 より，辺集合 \(E\) を \(2\) つの森 \(T_1, T_2\) に分解することができます．(各辺が \(T_1, T_2\) のどちらかに入る)

\((u, v) \in T_1\) であるとします．辺 \((u, v)\) を \(T_1\) から削除し，辺集合を元に戻すと，\(T_1\) において頂点 \(u, v\) が連結でなくなります．

Bob は，自分の手番で \(T_2\) から適切に辺を選んで削除することで，\(T_2\) においても頂点 \(u, v\) を非連結にすることができます．

この後，Alice と Bob が \(1\) 回ずつ手番を行っても，

• \(T_1, T_2\) は森である
• \(T_1, T_2\) の両方で頂点 \(u, v\) が非連結

を維持できることを示します．

Alice が辺 \((a, b) \in T_1\) に対して縮約を行ったとします．\(T_1\) については，森であること，\(u, v\) 間が非連結であることは維持されます．

\(T_2\) では以下のいずれかが起こります．

• \(a, b\) が \(T_2\) の同じ連結成分にある場合 : 縮約によって，サイクルが発生することがあります．発生した場合は，サイクルから \(1\) 本を削除して森であることを維持します．
• \(a, b\) が \(T_2\) の異なる連結成分にある場合 : 縮約によって，\(u, v\) 間が連結になることがあります．連結になった場合は，\(u - v\) パス上から \(1\) 本を削除して非連結であることを維持します．

以上により，Bob 勝ちであることが分かります．

勝敗判定のアルゴリズム

全域木が \(1\) つ存在するかどうかの判定は非常に簡単ですが，辺素な全域木が \(2\) つ存在するかの判定はかなり難しそうです．実際のところ，マトロイドの枠組みを使用して多項式時間でできることが知られています．

辺集合 \(E\) を台集合とし，\(E\) の部分集合であって森であるものを独立集合とするマトロイドを Graphic Matroid と言います．
同じ Graphic Matroid 2 つの合併 (Union) を取ると，「\(E\) の部分集合であって辺素な \(2\) つの森に分解できるもの」を独立集合とするマトロイドになります．(マトロイドの合併は再びマトロイドになることが知られています．)
合併後のマトロイドの独立集合判定・rank 判定は，元々のマトロイドの独立集合判定・rank 判定を多項式回行うことで求めることができます．

マトロイドの言葉を使うと，Shannon Switching Game の勝敗判定は以下のようになります．

与えられたグラフによる Graphic Matroid を \(\mathcal M\)，\(\mathcal M\) と \(\mathcal M\) の合併を \(\mathcal M^2\) と書く．
Bob が先手であるとき，\(\mathcal M^2\) 上で \(\operatorname{rank}(E) = \operatorname{rank}(E \cup \{(u, v)\}) \iff {}\)Alice 勝ち である．
Alice が先手であるとき，\(E\) に辺 \((u, v)\) を追加して Bob 先手とすれば良い．

---

一般のマトロイドの場合

Shannon Switching Game は，ゲームおよびその勝敗判定をマトロイドに拡張できることが知られています．

マトロイド \((E, \mathcal I)\) と目標となる要素 \(e \in E\) が与えられる．
(\(E\) はマトロイドの台集合，\(\mathcal I\) はマトロイドの独立集合の集まりである．)
Alice と Bob は交互に以下の操作を行う．

• Alice: \(x \in E \setminus \{e\}\) を \(1\) つ選び，マトロイドを \(x\) で縮約したものに変更する．
  
• Bob: \(x \in E \setminus \{e\}\) を \(1\) つ選び，マトロイドを \(x\) を除去したものに変更する．

\(\{e\} \notin \mathcal I\) となれば Alice の勝ち，最後まで \(\{e\} \in \mathcal I\) であれば Bob の勝ちである．

今回の問題では，\((\mathbb{F}_2)^{60}\) で線形独立ならば独立集合とする，Binary Matroid となっています．

Binary Matroid の合併上での rank を求めるには，各要素を順に追加して増加路を探す，基本の Matroid Union のアルゴリズムを適用すれば良いです．

参考になりそうな資料 : https://hitonanode.github.io/cplib-cpp/combinatorial_opt/matroid_union.hpp.html

\(L := \log_2 A_{\max}\) としたとき， 増加路を探すためのグラフの構築は，rank が増えたとき \(O(L^2)\) 時間，増えなかったとき \(O(L)\) 時間ででき，これを \(N\) 回行うので，全体で \(O(NL + L^3)\) 時間となります．(ここまで頑張らなくても， \(O(NL^3)\) 時間で AC できます．)