PKU 1632 Vase collection

http://poj.org/problem?id=1632
36種類の形と36種類の模様が存在するツボがある。
今、このうちのいくつかの形と模様の組み合わせられたツボがある。
ここでk種類の形とk種類の模様を指定した時、k*kの形と模様の組み合わせのツボがすべての存在するような最大のkを求めろというような問題。

深さ優先探索でTLEしたので、幅優先しました。

ll g[36];
ll r[36];
int ans;

bool can(ll st,int sz){
  ll ko=(1LL<<36)-1;
  rep(i,36){
    if(st&(1LL<<i))ko&=g[i];
  }
  int ok=0;
  rep(i,36){
    if((ko&(1LL<<i)) && (r[i]&st)==st)++ok;
  }
  return ok>=sz;
}

void solve(){
  int m;
  cin>>m;
  memset(g,0,sizeof(g));
  memset(r,0,sizeof(r));
  rep(i,m){
    ll a,b;
    cin>>a>>b;
    --a,--b;
    g[a]|=1LL<<b;
    r[b]|=1LL<<a;
  }
  ans=0;
  queue<pair<ll,ll> > q;
  q.push(mp(0,0));
  set<ll> app;
  while(!q.empty()){
    ll sz=q.front().F;
    ll st=q.front().S;
    q.pop();
    if(app.count(st))continue;
    ans=sz;
    app.insert(st);
    rep(i,36){
      if(st&(1LL<<i))continue;
      if(can(st|1LL<<i,sz+1))q.push(mp(sz+1,st|1LL<<i));
    }
  }
  cout<<ans<<endl;
}

main(){
  int T;
  cin>>T;
  while(T--)solve();
}