var BN=Import("zklBigNum");

const nMax=100, nBranches=4;

var rooted  =(nMax+1).pump(List.createLong(nMax+1).write,BN.fp(0)),
    unrooted=(nMax+1).pump(List.createLong(nMax+1).write,BN.fp(0));
rooted[0]=BN(1); rooted[1]=BN(1); unrooted[0]=BN(1); unrooted[1]=BN(1);

fcn tree(br,n,l,inSum,cnt){
   var c=(nBranches).pump(List().write,0);  // happens only once

   sum := inSum;
   foreach b in ([br + 1 .. nBranches]){
      sum += n;
      if (sum > nMax or (l * 2 >= sum and b >= nBranches)) return();
      if (b == br + 1) c[br] = rooted[n] * cnt; // -->BigInt
      else{
	 c[br].mul(rooted[n] + b - br - 1);
	 c[br].div(b - br);
      }
      if (l * 2 < sum) unrooted[sum].add(c[br]);
      if (b < nBranches) rooted[sum].add(c[br]);
      foreach m in ([n-1 .. 1,-1]) { tree(b, m, l, sum, c[br]); }
   }
}

fcn bicenter(s){
   if (s.isEven) unrooted[s].add(rooted[s / 2] * (rooted[s / 2] + 1) / 2);
}

foreach n in ([1 .. nMax]){
   tree(0, n, n, 1, BN(1));
   bicenter(n);
   println(n, ": ", unrooted[n]);
}