原题解链接:https://ac.nowcoder.com/discuss/150009

打表发现,对于n2n≥2,都是先手赢。

Winning. Ways.for. Your.Mathematical.Plays. V1 Chapter 7, P193中有对FusionPrincipleFusion Principle的证明,由此证明本题。

下面是FusionPrincipleFusion Principle的简要说明:

给出一个无向图和一个起点,AliceAliceBobBob在其上玩删边游戏,它的SGSG值在如下操作后不会改变:

  1. 将图中的任意一个偶环缩成一个新点;
  2. 任意一个奇环缩成一个新点加一个新边;
  3. 所有连到原先环上的边全部改为与新点相连。

#include<iostream>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T)
    {
        T--;
        int n;
        cin>>n;
        if(n==1)
            cout<<"Kozilek, Butcher of Truth"<<endl;
        else 
            cout<<"Ulamog, the Infinite Gyre"<<endl;
        
    }
    return 0;
}