@Override
	public DependencyInstance decode(DependencyInstance inst,
			LocalFeatureData lfd, GlobalFeatureData gfd, boolean addLoss) 
	{
		int N = inst.length;
        int M = N << 1;
        
        int[] deps = inst.heads;
        
        double[][] scores = new double[M][M];
        int[][] oldI = new int[M][M];
        int[][] oldO = new int[M][M];
        for (int i = 0; i < N; ++i)
            for (int j = 1; j < N; ++j) 
                if (i != j) {
                    oldI[i][j] = i;
                    oldO[i][j] = j;
                    double va = lfd.getArcScore(i,j);
                    if (addLoss && deps[j] != i) va += 1.0;                    
                    scores[i][j] = va;
                }

        boolean[] ok = new boolean[M];
        boolean[] vis = new boolean[M];
        boolean[] stack = new boolean[M];
        for (int i = 0; i < M; ++i) ok[i] = true;

        int[] final_par = new int[M];
        for (int i = 0; i < M; ++i) final_par[i] = -1;

        chuLiuEdmond(N, scores, ok, vis, stack, oldI, oldO, final_par);
        if (print) System.out.println();
        
		DependencyInstance predInst = new DependencyInstance(inst);
		predInst.heads = new int[N];
		predInst.deplbids = new int[N];
		
        for (int i = 1; i < N; ++i) {
            int j = final_par[i];
            predInst.heads[i] = j;
        }
        
        return predInst;
	}