Как улучшить временную сложность графа для поиска пути от src до des в java

Question

Здесь я пытаюсь напечатать Боба, если ни один из узлов на пути от src до dec нечетен, затем выведите Боба или Алекс. существует граф с N вершинами и N-1 ребрами. и Q не является путем для тех путей, которые вы должны напечатать Бобу или Алексу. Для меня время, потраченное на этот код, составляет 26,000000 секунд. Как это улучшить.

и возможно ли реализовать эту программу без рекурсии.

static class Graph{
    static ArrayList<Integer> arr[] ; 
    static int N;
        public Graph(int N) {
            this.N = N;
            arr = new ArrayList[N];

            for (int i=0;i<N;i++)
                arr[i] = new ArrayList<>();
            }

    public void addEdge(int u, int v) {
        arr[u-1].add(v-1);
        arr[v-1].add(u-1);

        }
    }
    static class Path{
        int u;
        int v;
        public Path(int u, int v) {
            super();
            this.u = u-1;
            this.v = v-1;
        }

    }
    public static void main(String[] args) {
        long beginTime = System.nanoTime();
        Scanner sc= new Scanner(System.in);
        int N= sc.nextInt();
        int Q= sc.nextInt();
        Graph  g = new Graph(N);
        for(int m=0;m<N-1;m++)
        {
            g.addEdge(sc.nextInt(),sc.nextInt());
        }
        List<Path> ll= new ArrayList<>();
        for(int i=0;i<Q;i++)
        {
            ll.add(new Path(sc.nextInt(),sc.nextInt()));
        }
             ll.forEach(s->printAllPaths(g,s.u, s.v));
         System.err.println("AmpleSyrup done in " + ((System.nanoTime() - beginTime) / 1e9) + " seconds.");
    }

     static void printAllPaths(Graph g,int s, int d)  
        { 
            boolean[] isVisited = new boolean[g.N]; 
            ArrayList<Integer> pathList = new ArrayList<>();
            pathList.add(s);
            printAllPathsUtil(g,s, d, isVisited, pathList); 
        } 

         static void printAllPathsUtil(
                Graph g,Integer u, Integer d, 
                                        boolean[] isVisited, 
                                List<Integer> localPathList) { 

            isVisited[u] = true; 

            if (u.equals(d))  
            { 
                if(localPathList.size()%2==0)
                    System.out.println("Alex");
                else
                    System.out.println("Bob");

                isVisited[u]= false; 
                return ; 
            } 
           for (Integer i : g.arr[u])  
            { 
                if (!isVisited[i]) 
                {   localPathList.add(i); 
                    printAllPathsUtil(g,i, d, isVisited, localPathList); 
                    localPathList.remove(i); 
                } 
            } 
           isVisited[u] = false; 
        }