 y = id_in_node[T];
    // printf("LCA=%d x=%d y=%d\n",LCA,x,y);
    while (node[x].father!= LCA) {
        push_borders_up_path(x, dist[0]);
        x = node[x].father;
    }
    while (node[y].father!= LCA) {
        push_borders_up_path(y, dist[1]);
        y = node[y].father;
    }
    std::vector<int> id[2];
    for (int t = 0; t < 2; t++) {
        if (t == 0)
            p = x;
        else
            p = y;
        for (i = j = 0; i < (int)dist[t].size(); i++)
            if (node[p].border_in_father[i]!= -1) {
                id[t].push_back(node[p].border_in_father[i]);
                dist[t][j] = dist[t][i];
                j++;
            }
        while (dist[t].size() > id[t].size()) {
            dist[t].pop_back();
        }
    }
    int MIN = INF;
    int S_ = -1, T_ = -1;
    for (i = 0; i < (int)dist[0].size(); i++)
        for (j = 0; j < (int)dist[1].size(); j++) {
            k = dist[0][i] + dist[1][j] +
                node[LCA].dist.a[id[0][i]][id[1][j]];
            if (k < MIN) {
                MIN = k;
                S_ = id[0][i];
                T_ = id[1][j];
            }
        }
    if (MIN < INF) {
        for (int t = 0; t < 2; t++) {
            int p, now;
            if (t == 0)
                p = x, now = node[LCA].border_in_son[S_];
            else
                p = y, now = node[LCA].border_in_son[T_];
            while (node[p].n > 1) {
                // printf("t=%d p=%d now=%d
                // node[p].path_record[now]=%d\n",t,p,now,node[p].path_record[now]);
                if (node[p].path_record[now] >= 0) {
                    find_path_border(p, now, node[p].path_record[now],
                                     order, 0);
                    now = node[p].path_record[now];
                } else if (node[p].path_record[now] > -INF) {
                    int temp = now;
                    now = node[p].border_in_son[now];
                    p = -node[p].path_record[temp];
                } else
                    break;
            }
            if (t == 0) {
                reverse(order.begin(), order.end());
                order.push_back(node[LCA].border_id[S_]);
                find_path_border(LCA, S_, T_, order, 0);
            }
        }
    }
    return MIN;
    // cout<<"QY5";
}

int G_Tree::real_border_number(int x) {
    int i, j, re = 0, id;
    std::map<int, int> vis;
    for (i = 0; i < node[x].G.n; i++)
        vis[node[x].G.id[i]] = 1;
    for (i = 0; i < node[x].G.n; i++) {
        id = node[x].G.id[i];
        for (j = G.head[id]; j; j = G.next[j])
            if (vis[G.list[j]] == 0) {
                re++;
                break;
            }
    }
    return re;
}

void G_Tree::find_path_border(int x, int S, int T, std::vector<int> &v, int rev) {
    /*printf("find:x=%d S=%d T=%d\n",x,S,T);
    printf("node:%d\n",x);
    node[x].write();
    printf("\n\n\n\n");*/
    if (node[x].order.a[S][T] == -1) {
        if (rev == 0)
            v.push_back(node[x].border_id[T]);
        else
            v.push_back(node[x].border_id[S]);
    } else if (node[x].order.a[S][T] == -2) {
        find_path_border(node[x].father, node[x].border_in_father[S],
                         node[x].border_in_father[T], v, rev);
    } else if (node[x].order.a[S][T] == -3) {
        find_path_border(
            node[x].son[node[x].color[node[x].border_id_innode[S]]],
            node[x].border_in_son[S], node[x].border_in_son[T], v, rev);
    } else if (node[x].order.a[S][T] >= 0) {
        int k = node[x].order.a[S][T];
        if (rev == 0) {
            find_path_border(x, S, k, v, rev);
            find_path_border(x, k, T, v, rev);
        } else {
            find_path_border(x, k, T, v, rev);
            find_path_border(x, S, k, v, rev);
        }
    }
}

std::vector<int> G_Tree::KNN(int S, int K, std::vector<int> T) {
    std::priority_queue<int> K_Value;
    std::vector<std::pair<int, int>> query;
    for (int i = 0; i < (int)T.size(); i++)
        query.push_back(std::make_pair(
            -node[find_LCA(id_in_node[S], id_in_node[T[i]])].deep, i));
    sort(query.begin(), query.end());
    std::vector<int> re, ans;
    if (K <= 0)
        return re;
    for (int i = 0; i < (int)T.size(); i++) {
        int bound = (int)K_Value.size() < K? INF : K_Value.top();
        // if(bound==INF)printf("- ");else printf("%d ",bound);
        if (Optimization_KNN_Cut)
            ans.push_back(search_catch(S, T[query[i].second], bound));
        else
            ans.push_back(search_catch(S, T[query[i].second]));
        if ((int)K_Value.size() < K)
            K_Value.push(ans[i]);
        else if (ans[i] < K_Value.top()) {
            K_Value.pop();
            K_Value.push(ans[i]);
        }
    }
    int bound = ((int)ans.size() <= K)? INF : K_Value.top();
    for (int i = 0; i < (int)T.size() && (int)re.size() < K; i++)
        if (ans[i] <= bound)
            re.push_back(query[i].second);
    sort(re.begin(), re.end());
    return re;
}

std::vector<int> G_Tree::KNN(int S, int K, std::vector<int> T,
                     std::vector<int> offset) {
    std::priority_queue<int> K_Value;
    std::vector<std::pair<int, int>> query;
    for (int i = 0; i < (int)T.size(); i++)
        query.push_back(std::make_pair(
            -node[find_LCA(id_in_node[S], id_in_node[T[i]])].deep, i));
    sort(query.begin(), query.end());