Planets Queries II - Implementation

Here is the functional graph query implementation:

function planetsQueriesII(n, f, queries):
    // Find cycles and label nodes
    cycleId = array of size n, all -1
    distToCycle = array of size n, all -1
    cyclePos = array of size n, all -1
    cycleLen = array of size n, all 0
    visited = array of size n, all 0  // 0=unvisited, 1=in-progress, 2=done

    function dfs(u, path):
        if visited[u] == 2:
            return
        if visited[u] == 1:
            // Found cycle
            cycleStart = path.indexOf(u)
            len = path.length - cycleStart
            for i from cycleStart to path.length - 1:
                v = path[i]
                cycleId[v] = u
                cyclePos[v] = i - cycleStart
                cycleLen[v] = len
            return

        visited[u] = 1
        path.append(u)
        dfs(f[u], path)
        visited[u] = 2

    for i from 0 to n - 1:
        if visited[i] == 0:
            dfs(i, [])

    // Compute distance to cycle for non-cycle nodes
    // Build binary lifting table
    up = 2D array of size n x LOG
    for i from 0 to n - 1:
        up[i][0] = f[i]
    for j from 1 to LOG - 1:
        for i from 0 to n - 1:
            up[i][j] = up[up[i][j-1]][j-1]

    function query(a, b):
        // Check if b is reachable from a
        // Case 1: Both in same tree branch
        // Case 2: Both in same cycle
        // Use binary lifting + cycle arithmetic

    for (a, b) in queries:
        print query(a, b)

Time: $O((n + q) \log n)$. Space: $O(n \log n)$.