Recently I'm trying to solve UVa-10938. My solution has given correct answer for all available cases and also for the cases given in uDebug cases. But I still getting wrong answer :( , I don't understand why.

My approach is finding the LCA(Lowest Common Ancestor) for the given pair in the query and find the path between two node. If the path has odd number of edges than I find a(middle node in the path) and b(next of the middle node in the path), And there is an infinite lope between this two nodes.

On the other hand, if the path has even number of edges, than I find a(middle node in the path), And both flea meet in a.

Please help me to debug by providing some test cases where my solution will give wrong answer. Here's the code.

using namespace std;

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>


#define ll long long
#define MAXN 5001
#define LOGN 14


bool visit[MAXN];
ll par[MAXN][LOGN], level[MAXN];
vector<ll> v[MAXN];


void DFS(ll src, ll lev)
{
    visit[src] = true;
    level[src] = lev;

    for(ll i=0; i<v[src].size(); i++){
        ll temp = v[src][i];

        if(!visit[temp]){
            par[temp][0] = src;
            DFS(temp, lev+1);
        }
    }
}


void PreProcess(ll n)
{
    for(ll i=1; i<LOGN; i++){
        for(ll j=1; j<=n; j++){
            if(par[j][i-1]!=-1) par[j][i] = par[par[j][i-1]][i-1];
        }
    }
}

ll LCA(ll a,ll b)
{
    ll log = 0, temp;

    if(level[a]<level[b]){
        temp = a;
        a = b;
        b = temp;
    }

    while(1){
        temp = log+1;
        if((1<<temp)>level[a]) break;
        log++;
    }

    for(ll i=log; i>=0; i--){
        if(par[a][i]!=-1 && level[par[a][i]]>=level[b]) a = par[a][i];
    }

    if(a==b) return a;

    for(ll i=log; i>=0; i--){
        if(par[a][i]!=-1 && par[a][i]!=par[b][i]) a = par[a][i], b = par[b][i];
    }

    return par[a][0];
}

void Func(ll a, ll b)
{
    ll mid = LCA(a,b), k, up, log = 0;
    up = level[a] + level[b] - 2*level[mid];
    k = level[a] - up/2;
    ///cout<<mid<<" "<<k<<"\n";
    if(level[mid]>=k){
        a = b;
        k = level[a] - up/2;
    }

    while(1){
        ll temp = log + 1;
        if((1<<temp)>level[a]) break;
        log++;
    }

    for(ll i=log; i>=0; i--){
        if(par[a][i]!=-1 && level[par[a][i]]>=k) a = par[a][i];
    }

    if(up%2){
        b = par[a][0];
        cout<<"The fleas jump forever between "<<min(a,b)<<" and "<<max(a,b)<<".\n";
    }
    else cout<<"The fleas meet at "<<a<<".\n";
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ///freopen("test.txt","w",stdout);
    ll n;

    while(cin>>n && n){
        ll a, b, q;

        for(ll i=1; i<n; i++){
            cin>>a>>b;

            v[a].push_back(b);
            v[b].push_back(a);
        }

        memset(visit, false, sizeof(visit));
        par[1][0] = -1;
        DFS(1,0);
        PreProcess(n);

        cin>>q;

        for(ll i=0; i<q; i++){
            cin>>a>>b;
            Func(a,b);
        }

        for(ll i=1; i<=n; i++) v[i].clear();
    }

return 0;
}