cool link to understand hackenbush and colon principle

cbuff's link and dingma129's post is really helpful, thnx^^ but if u need code:

int gr[501];

int dfs(int u, int p, vector<vector<int>>& G){
    for(auto ch : G[u]){
        if(ch != p) gr[u] ^= dfs(ch,u,G);
    }
    return u == 1 ? gr[u] : ++gr[u];
}


string deforestation(int n, vector<vector<int>> tree) {
    memset(gr, 0, sizeof(gr));
    vector<vector<int>> G(n+1);
    for(auto p : tree){
        G[p[0]].push_back(p[1]);
        G[p[1]].push_back(p[0]);
    }
    return dfs(1,-1,G) ? "Alice" : "Bob";
}

just a useful quick note about computing the nimber for such a game:

When played with a forest of “trees” (Colon Principle): When branches come together at a vertex, one may replace the branches by a non-branching stalk of length equal to their nim sum.

reference: http://web.mit.edu/sp.268/www/nim.pdf page 19

Can anyone explain why Alice will select 3->4? Why can't he choose 1->2 or 1->3??

import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;

public class Solution {

static int[] a,b;//0-index
static int[] c;//1-index
static int[] d;//1-index
static int n;

public static void main(String[] args) throws IOException{
    new Solution().run();
}

public static void dfscol(int root){
    d[root]=1;
    for(int i=0;i<n-1;i++){
        if(a[i]==root && d[b[i]]==0){
            dfscol(b[i]);
            c[root]++;
        }
        if(b[i]==root && d[a[i]]==0){
            b[i]=a[i]; 
            a[i]=root;
            dfscol(b[i]);
            c[root]++;
        }
    }
    return;
}

public static int dfs(int root){
    if(root > 0 && root <=n){
        if(c[root]==0) {//leaf
            return 0;
        }
        else {//c[root]>0
            int count =0;
            for(int i=0;i<n-1;i++){
                if(a[i]==root){
                    count^=(int)(1+dfs(b[i]));
                }
            }
            return count;
        }
    }
    return 0;
}

public void run() throws IOException{
   Scanner in = new Scanner(System.in);
   BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    int t = in.nextInt();
    int i,u,v, counter;
    a = new int[501];
    b = new int[501];
    c = new int[501];
    d = new int[501];

    for(int tt =0;tt<t;tt++){
        Arrays.fill(c,0);
        Arrays.fill(d,0);

        n = in.nextInt();//n<=500
        counter = 0;

        for(i=0;i<n-1;i++){
            u = in.nextInt();//n<=500 
            v = in.nextInt();//n<=500
            a[i]=u;
            b[i]=v;
        }

        d[1]=1;
        dfscol(1);

        //dfs
        counter = dfs(1);
        //System.out.println("Node "+1+": "+counter);
        if(counter>0) log.write("Alice\n");
        else log.write("Bob\n");
    }
    log.flush();

} }