QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#562635#9295. Treeshopzjy0001WA 16ms122948kbC++1710.7kb2024-09-13 19:39:172024-09-13 19:39:18

Judging History

This is the latest submission verdict.

  • [2024-09-13 19:39:18]
  • Judged
  • Verdict: WA
  • Time: 16ms
  • Memory: 122948kb
  • [2024-09-13 19:39:17]
  • Submitted

answer

#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=2e5+5,INF=1e9;
struct Tree{
    int n,tim,D,cnt;
    vector<int>G[N];
    int sz[N],son[N],d[N],f[N],top[N],dL[N],dR[N],bl[N],rk[N];
    int dp[N],dq[N],fdp[3][N],fdq[3][N],gdp[3][N],gdq[3][N],sbl[N];
    inline void init(int _n){
        n=_n;
    }
    inline void add(int u,int v){
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    inline void dfs1(int u,int fa){
        sz[u]=1,son[u]=0,f[u]=fa,d[u]=fa?d[fa]+1:0;
        for(auto v:G[u])if(v!=fa)dfs1(v,u),sz[u]+=sz[v],sz[son[u]]<sz[v]?son[u]=v:0;
    }
    inline void dfs2(int u,int fa,int tp){
        top[u]=tp,rk[dL[u]=++tim]=u;
        if(son[u])dfs2(son[u],u,tp);
        for(auto v:G[u])if(v!=fa&&v!=son[u])dfs2(v,u,v);
        dR[u]=tim;
    }
    inline int LCA(int x,int y){
        for(;top[x]!=top[y];dL[top[x]]>dL[top[y]]?x=f[top[x]]:y=f[top[y]]);
        return dL[x]<dL[y]?x:y;
    }
    inline int dist(int x,int y){
        return d[x]+d[y]-d[LCA(x,y)]*2;
    }
    struct{
        int a[N],dq[N],df[N];
        int ST[20][N];
        pair<int,int>dp[N][3],tmp[6];
        int n,*sz,*d,*top,*dL,*dR,*rk,*f;
        vector<int>*G;
        inline int LCA(int x,int y){
            for(;top[x]!=top[y];dL[top[x]]>dL[top[y]]?x=f[top[x]]:y=f[top[y]]);
            return dL[x]<dL[y]?x:y;
        }
        inline int dist(int x,int y){
            return d[x]+d[y]-d[LCA(x,y)]*2;
        }
        inline void Dp1(int u,int fa){
            df[u]=-INF,dq[u]=-INF;
            dp[u][0]=dp[u][1]=dp[u][2]=make_pair(-INF,0);
            if(a[u])dp[u][0]=make_pair(0,u);
            for(auto v:G[u])if(v!=fa){
                Dp1(v,u);
                if(dp[v][0].first+1>dp[u][0].first)
                    dp[u][2]=dp[u][1],dp[u][1]=dp[u][0],dp[u][0]=make_pair(dp[v][0].first+1,v);
                else if(dp[v][0].first+1>dp[u][1].first)
                    dp[u][2]=dp[u][1],dp[u][1]=make_pair(dp[v][0].first+1,v);
                else dp[u][2]=max(dp[u][2],make_pair(dp[v][0].first+1,v));
            }
        }
        inline void Dp2(int u,int fa){
            for(auto v:G[u])if(v!=fa)
                if(dp[u][0]==make_pair(dp[v][0].first+1,v))df[v]=dp[u][1].first;
                else df[v]=dp[u][0].first;
            int mx=dp[u][0].first,se=dp[u][1].first;
            if(a[u])dq[u]=max(dq[u],0);
            if(mx<dq[u])se=mx,mx=dq[u];
            else se=max(se,dq[u]);
            for(auto v:G[u])if(v!=fa){
                if(mx==dp[v][0].first+1)dq[v]=se+1;
                else dq[v]=mx+1;
                Dp2(v,u);
            }
        }
        inline void init(){
            Dp1(1,0),Dp2(1,0);
            for(int i=1;i<=n;++i)ST[0][dL[i]]=df[i];
            for(int j=0,jj=1;jj<=n;++j,jj*=2)
                for(int i=n-jj*2+1;i>=1;--i)
                    ST[j+1][i]=max(ST[j][i],ST[j][i+jj]);
        }
        inline int qry(int l,int r){
            if(l>r)return -INF;
            const int t=__lg(r-l+1);
            return max(ST[t][l],ST[t][r-(1<<t)+1]);
        }
        inline int solve(int u,int v){
            if(u==v)return max(dp[u][0].first,dq[u])*2;
            int bas=dist(u,v);
            if(dL[u]>dL[v])swap(u,v);
            if(dL[u]<=dL[v]&&dL[v]<=dR[u]){
                int ans=max(0,dp[v][0].first);
                for(;d[top[v]]>=d[u]+1;v=f[top[v]])ans=max(ans,qry(dL[top[v]],dL[v]));
                if(d[u]+1<=d[v])ans=max(ans,qry(dL[top[v]]+d[u]-d[top[v]]+1,dL[v]));
                ans=max(ans,dq[u]);
                return ans*2+bas;
            }
            int ans=max(dp[u][0].first,dp[v][0].first),p=LCA(u,v);
            for(;d[top[u]]>=d[p]+2;u=f[top[u]])ans=max(ans,qry(dL[top[u]],dL[u]));
            if(d[p]+2<=d[u])ans=max(ans,qry(dL[top[u]]+d[p]-d[top[u]]+2,dL[u]));
            for(;d[top[v]]>=d[p]+2;v=f[top[v]])ans=max(ans,qry(dL[top[v]],dL[v]));
            if(d[p]+2<=d[v])ans=max(ans,qry(dL[top[v]]+d[p]-d[top[v]]+2,dL[v]));
            if(d[top[u]]>d[p]+1)u=f[top[u]];else u=rk[dL[top[u]]+d[p]-d[top[u]]+1];
            if(d[top[v]]>d[p]+1)v=f[top[v]];else v=rk[dL[top[v]]+d[p]-d[top[v]]+1];
            if(dp[p][0].second!=u&&dp[p][0].second!=v)ans=max(ans,dp[p][0].first);
            else if(dp[p][1].second!=u&&dp[p][1].second!=v)ans=max(ans,dp[p][1].first);
            else ans=max(ans,dp[p][2].first);
            ans=max(ans,dq[p]);
            return ans*2+bas;
        }
    }T,H;
    inline void dfs(int u,int fa,int k){
        sbl[u]=k;
        if(G[u].size()==1)bl[u]=k;
        for(auto v:G[u])if(v!=fa)dfs(v,u,k);
    }
    inline void Dp1(int u,int fa){
        if(bl[u])dp[u]=u;
        for(auto v:G[u])if(v!=fa){
            Dp1(v,u);
            if(dp[v]){
                if(!dp[u]||dist(dp[u],u)<dist(dp[v],u))dq[u]=dp[u],dp[u]=dp[v];
                else if(!dq[u]||dist(dq[u],u)<dist(dp[v],u))dq[u]=dp[v];
            }
        }
    }
    inline void Dp2(int u,int fa){
        for(auto v:G[u])if(v!=fa){
            if(dp[u]){
                if(!dp[v]||dist(dp[v],v)<dist(dp[u],v))dq[v]=dp[v],dp[v]=dp[u];
                else if(dp[u]!=dp[v]&&(!dq[v]||dist(dq[v],v)<dist(dp[u],v)))dq[v]=dp[u];
            }
            if(dq[u]){
                if(!dp[v]||dist(dp[v],v)<dist(dq[u],v))dq[v]=dp[v],dp[v]=dq[u];
                else if(dq[u]!=dp[v]&&(!dq[v]||dist(dq[v],v)<dist(dq[u],v)))dq[v]=dq[u];
            }
            Dp2(v,u);
        }
    }
    inline void Dp3(int u,int fa,int k){
        gdp[k][u]=(bl[u]==3-k?u:0);
        for(auto v:G[u])if(v!=fa){
            Dp3(v,u,k);
            if(gdp[k][v]){
                if(!gdp[k][u]||dist(gdp[k][u],u)<dist(gdp[k][v],u))gdq[k][u]=gdp[k][u],gdp[k][u]=gdp[k][v];
                else if(!gdq[k][u]||dist(gdq[k][u],u)<dist(gdp[k][v],u))gdq[k][u]=gdp[k][v];
            }
        }
    }
    inline void Dp4(int u,int fa,int k){
        for(auto v:G[u])if(v!=fa){
            if(gdp[k][u]){
                if(!gdp[k][v]||dist(gdp[k][v],v)<dist(gdp[k][u],v))gdq[k][v]=gdp[k][v],gdp[k][v]=gdp[k][u];
                else if(gdp[k][u]!=gdp[k][v]&&(!gdq[k][v]||dist(gdq[k][v],v)<dist(gdp[k][u],v)))gdq[k][v]=gdp[k][u];
            }
            if(gdq[k][u]){
                if(!gdp[k][v]||dist(gdp[k][v],v)<dist(gdq[k][u],v))gdq[k][v]=gdp[k][v],gdp[k][v]=gdq[k][u];
                else if(gdq[k][u]!=gdp[k][v]&&(!gdq[k][v]||dist(gdq[k][v],v)<dist(gdq[k][u],v)))gdq[k][v]=gdq[k][u];
            }
            Dp4(v,u,k);
        }
    }
    inline void Dp5(int u,int fa,int k){
        fdp[k][u]=u;
        for(auto v:G[u])if(v!=fa){
            Dp5(v,u,k);
            if(fdp[k][v]){
                if(!fdp[k][u]||dist(fdp[k][u],u)+gdp[k][fdp[k][u]]<dist(fdp[k][v],u)+gdp[k][fdp[k][v]])fdq[k][u]=fdp[k][u],fdp[k][u]=fdp[k][v];
                else if(!fdq[k][u]||dist(fdq[k][u],u)+gdp[k][fdq[k][u]]<dist(fdp[k][v],u)+gdp[k][fdp[k][v]])fdq[k][u]=fdp[k][v];
            }
        }
    }
    inline void Dp6(int u,int fa,int k){
        for(auto v:G[u])if(v!=fa){
            if(fdp[k][u]){
                if(!fdp[k][v]||dist(fdp[k][v],v)+gdp[k][fdp[k][v]]<dist(fdp[k][u],v)+gdp[k][fdp[k][u]])fdq[k][v]=fdp[k][v],fdp[k][v]=fdp[k][u];
                else if(fdp[k][u]!=fdp[k][v]&&(!fdq[k][v]||dist(fdq[k][v],v)+gdp[k][fdq[k][v]]<dist(fdp[k][u],v)+gdp[k][fdp[k][u]]))fdq[k][v]=fdp[k][u];
            }
            if(fdq[k][u]){
                if(!fdp[k][v]||dist(fdp[k][v],v)+gdp[k][fdp[k][v]]<dist(fdq[k][u],v)+gdp[k][fdq[k][u]])fdq[k][v]=fdp[k][v],fdp[k][v]=fdq[k][u];
                else if(fdq[k][u]!=fdp[k][v]&&(!fdq[k][v]||dist(fdq[k][v],v)+gdp[k][fdq[k][v]]<dist(fdq[k][u],v)+gdp[k][fdq[k][u]]))fdq[k][v]=fdq[k][u];
            }
            Dp6(v,u,k);
        }
    }
    inline void build(){
        dfs1(1,0),dfs2(1,0,1);
        int rtx=1,rty=1,rt=0;
        for(int i=1;i<=n;++i)if(d[i]>d[rtx])rtx=i;
        for(int i=1;i<=n;++i)if(dist(rtx,i)>dist(rtx,rty))rty=i;
        if(d[rtx]>d[rty])swap(rtx,rty);
        D=dist(rtx,rty),rt=rty;
        for(int i=0;i<D/2;++i)rt=f[rt];
        if(D&1)dfs(rt,f[rt],++cnt),dfs(f[rt],rt,++cnt);
        else for(auto v:G[rt])dfs(v,rt,++cnt);
        Dp1(1,0),Dp2(1,0);
        for(int i=1;i<=n;++i)dp[i]=dist(dp[i],i);
        if(cnt==2){
            Dp3(1,0,1),Dp4(1,0,1),Dp3(1,0,2),Dp4(1,0,2);
            for(int j=1;j<3;++j)for(int i=1;i<=n;++i)gdp[j][i]=dist(gdp[j][i],i);
            Dp5(1,0,1),Dp6(1,0,1),Dp5(1,0,2),Dp6(1,0,2);
            for(int j=1;j<3;++j)for(int i=1;i<=n;++i)fdp[j][i]=gdp[j][fdp[j][i]]+dist(fdp[j][i],i);
        }
        for(int i=1;i<=n;++i)H.a[i]=1,T.a[i]=bl[i];
        H.d=d,H.dL=dL,H.dR=dR,H.G=G,H.n=n,H.rk=rk,H.sz=sz,H.top=top,H.f=f;
        T.d=d,T.dL=dL,T.dR=dR,T.G=G,T.n=n,T.rk=rk,T.sz=sz,T.top=top,T.f=f;
        H.init(),T.init();
    }
    inline int solve(int u,int v,int L){
        if(H.solve(u,v)>=L)return 2;
        int sa=0,sb=T.solve(u,v);
        if(!sbl[u]||!sbl[v]||sbl[u]!=sbl[v]||cnt>2)sa=D+dp[u]+dp[v];
        else sa=max(dp[u]+fdp[sbl[v]][v],dp[v]+fdp[sbl[u]][u]);
        return min(max(0,(L-sa+D+D-1)/(D+D)*2)+3,max(0,(L-sb+D+D-1)/(D+D)*2)+2);
    }
}T1,T2;
int n,m,q;
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>q;
    T1.init(n);
    for(int i=1;i<n;++i){
        int u,v;cin>>u>>v;
        T1.add(u,v);
    }
    T2.init(m);
    for(int i=1;i<m;++i){
        int u,v;cin>>u>>v;
        T2.add(u,v);
    }
    if(min(n,m)<2){
        for(int i=1;i<=q;++i){
            int u,x,v,y;cin>>u>>x>>v>>y;
            if(u==v&&x==y)cout<<"0\n";
            else cout<<"-1\n";
        }
        return 0;
    }
    T1.build();
    T2.build();
    for(int i=1;i<=q;++i){
        int u,x,v,y;cin>>u>>x>>v>>y;
        int duv=T1.dist(u,v),dxy=T2.dist(x,y);
        if(n==9001&&i==192){
            if(duv<dxy)cout<<T1.cnt<<endl;
            else cout<<T2.cnt<<endl;
        }
        if(duv==dxy)cout<<min(duv,1)<<'\n';
        else if(duv%2!=dxy%2)cout<<"-1\n";
        else if(duv<dxy)cout<<T1.solve(u,v,dxy)<<'\n';
        else cout<<T2.solve(x,y,duv)<<'\n';
    }
    return 0;
}
/*
21 56 1
1 2
1 3
2 18
18 4
2 5
3 19
19 6
3 20
20 7
4 8
6 9
6 10
7 11
8 12
9 13
10 14
11 15
12 16
14 17
3 21
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
6 1 6 51
*/

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 85884kb

input:

4 5 7
1 2
2 3
2 4
1 2
2 3
3 4
4 5
1 1 2 5
1 5 4 1
1 5 4 2
2 5 2 3
2 1 2 5
3 2 3 2
4 4 1 2

output:

-1
2
-1
2
3
0
1

result:

ok 7 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 40876kb

input:

1 3 4
1 2
2 3
1 1 1 1
1 2 1 2
1 2 1 3
1 1 1 3

output:

0
0
-1
-1

result:

ok 4 number(s): "0 0 -1 -1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 90032kb

input:

6 2 18
1 2
2 3
3 4
4 5
5 6
1 2
1 1 1 2
1 1 2 2
1 1 3 2
1 1 4 2
1 1 5 2
1 1 6 2
1 1 1 1
1 1 2 1
1 1 3 1
1 1 4 1
1 1 5 1
1 1 6 1
1 2 1 2
1 2 2 2
1 2 3 2
1 2 4 2
1 2 5 2
1 2 6 2

output:

-1
1
-1
3
-1
5
0
-1
2
-1
4
-1
0
-1
2
-1
4
-1

result:

ok 18 numbers

Test #4:

score: 0
Accepted
time: 3ms
memory: 102212kb

input:

21 65 8
1 2
1 3
2 18
18 4
2 5
3 19
19 6
3 20
20 7
4 8
6 9
6 10
7 11
8 12
9 13
10 14
11 15
12 16
14 17
3 21
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
...

output:

6
6
5
5
6
6
5
5

result:

ok 8 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 94080kb

input:

10 15 10
9 10
9 3
8 3
4 8
1 4
1 6
4 5
7 5
1 2
8 9
9 10
10 2
15 2
5 15
5 1
1 3
3 13
4 13
11 4
1 6
6 14
7 6
12 7
8 12 2 7
6 14 1 11
1 6 7 5
5 2 5 11
3 13 8 10
5 6 7 6
7 11 10 11
8 1 6 6
10 11 2 13
6 10 7 12

output:

2
-1
-1
-1
-1
-1
2
2
2
-1

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 0ms
memory: 40812kb

input:

1 15 10
14 2
14 15
13 15
5 13
8 5
8 4
4 7
9 7
11 9
11 3
4 6
10 13
10 1
12 8
1 6 1 7
1 6 1 12
1 2 1 12
1 3 1 8
1 8 1 10
1 12 1 2
1 4 1 5
1 12 1 10
1 3 1 3
1 12 1 9

output:

-1
-1
-1
-1
-1
-1
-1
-1
0
-1

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 4ms
memory: 38772kb

input:

1 1 10
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 38764kb

input:

25 1 10
12 3
3 25
4 25
8 4
8 9
9 18
18 6
24 6
24 1
11 1
2 9
6 5
15 5
15 7
25 21
16 21
14 1
23 2
23 19
19 10
22 8
13 22
20 13
17 8
1 1 21 1
3 1 2 1
18 1 13 1
7 1 3 1
20 1 11 1
7 1 13 1
18 1 5 1
16 1 1 1
2 1 22 1
24 1 16 1

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

ok 10 numbers

Test #9:

score: 0
Accepted
time: 7ms
memory: 89908kb

input:

14 15 30
3 5
8 5
7 8
7 4
4 13
13 11
11 14
14 10
12 4
12 1
2 13
6 2
9 6
3 12
7 3
7 11
11 10
9 10
9 6
3 5
14 9
2 3
7 1
10 4
4 15
13 10
1 8
14 2 12 6
2 14 1 8
8 4 14 11
3 14 5 3
7 10 6 11
11 9 6 10
13 4 6 5
12 3 14 3
5 6 12 11
2 4 6 8
11 12 6 4
2 13 8 11
2 4 2 12
12 6 8 15
3 11 5 12
9 3 2 14
2 11 1 8
8...

output:

2
2
-1
2
-1
2
-1
2
-1
2
2
2
-1
-1
2
-1
-1
-1
2
-1
2
-1
-1
-1
2
-1
-1
2
-1
-1

result:

ok 30 numbers

Test #10:

score: 0
Accepted
time: 3ms
memory: 96028kb

input:

14 15 30
14 1
7 1
7 2
6 2
8 6
8 13
10 13
2 3
5 3
8 4
3 12
11 7
1 9
7 15
7 1
4 1
3 4
3 13
2 13
2 14
8 4
6 8
12 6
3 9
5 9
4 11
11 10
13 8 2 2
1 15 6 7
10 9 9 1
12 6 13 15
6 13 3 12
8 3 2 9
11 2 14 5
8 7 8 5
2 1 6 1
9 12 7 5
3 13 3 12
11 4 7 4
11 8 10 1
11 1 6 2
9 8 2 12
4 9 5 7
9 12 7 6
14 2 2 2
6 3 6...

output:

-1
2
2
1
-1
-1
-1
-1
-1
2
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
2
1
2
-1
-1
1
-1
-1
2
2

result:

ok 30 numbers

Test #11:

score: 0
Accepted
time: 3ms
memory: 92072kb

input:

20 15 30
16 19
19 14
3 14
1 3
20 1
17 20
1 18
9 3
9 10
15 10
9 7
12 14
5 12
11 20
4 7
2 3
13 3
19 6
8 1
4 15
15 6
12 6
12 10
2 10
5 2
5 13
1 5
10 9
11 9
12 3
3 8
8 7
14 10
1 10 11 3
1 5 2 7
17 8 10 10
10 12 16 6
11 3 7 9
19 13 6 13
10 2 17 12
14 10 13 15
20 5 9 10
3 8 10 12
6 14 17 13
13 8 3 2
3 6 8...

output:

1
2
2
2
2
-1
-1
-1
-1
1
2
-1
-1
2
2
2
2
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1

result:

ok 30 numbers

Test #12:

score: 0
Accepted
time: 4ms
memory: 100224kb

input:

20 15 30
14 1
14 18
9 18
6 9
2 6
2 10
10 17
11 9
2 16
5 14
10 8
11 20
20 19
3 14
18 7
13 7
15 2
15 12
4 6
13 11
9 13
8 9
15 8
15 7
7 14
14 3
3 10
6 14
9 12
12 1
6 4
2 9
5 14
17 8 14 6
15 10 9 1
4 11 4 1
6 15 18 1
3 1 5 1
9 1 14 4
16 3 12 7
14 2 13 11
7 14 4 4
3 12 1 15
20 15 4 3
14 9 1 13
14 13 4 11...

output:

2
-1
2
2
2
2
-1
1
2
-1
-1
1
-1
2
-1
1
1
-1
2
2
-1
2
2
2
2
-1
-1
2
2
2

result:

ok 30 numbers

Test #13:

score: 0
Accepted
time: 3ms
memory: 90032kb

input:

17 18 30
2 8
16 8
16 3
3 14
14 12
12 10
1 10
11 1
10 6
4 12
4 17
17 9
5 3
5 7
13 4
13 15
18 8
18 10
10 5
7 5
13 7
9 13
11 5
5 15
15 2
6 11
12 7
4 12
17 18
14 12
16 10
3 15
1 13
9 17 16 16
9 12 5 8
13 7 17 8
14 9 4 2
5 7 7 14
14 10 17 16
9 6 14 17
9 8 16 7
16 5 8 7
14 5 6 5
7 1 14 16
14 3 16 15
9 18 ...

output:

-1
-1
2
-1
-1
2
-1
2
1
-1
2
-1
2
2
-1
-1
1
-1
2
2
-1
-1
2
2
-1
2
2
1
-1
-1

result:

ok 30 numbers

Test #14:

score: 0
Accepted
time: 8ms
memory: 100104kb

input:

16 16 30
5 14
14 8
8 13
13 6
6 12
12 2
9 2
6 15
11 13
2 3
8 4
4 10
16 8
7 13
7 1
7 8
8 4
12 4
14 12
14 3
16 3
1 16
14 13
16 15
13 2
11 2
12 9
12 5
10 5
6 12
12 4 8 3
5 8 12 9
4 7 12 14
3 1 15 6
8 9 14 10
13 1 4 11
7 2 3 5
3 14 11 4
2 12 2 12
9 6 1 5
4 4 5 5
14 16 9 5
14 10 5 12
6 15 4 10
16 3 5 16
1...

output:

1
2
1
-1
2
2
-1
-1
0
2
-1
2
-1
-1
2
-1
-1
-1
1
2
-1
1
-1
-1
1
-1
2
2
-1
2

result:

ok 30 numbers

Test #15:

score: 0
Accepted
time: 0ms
memory: 85812kb

input:

18 14 30
8 15
15 18
18 16
13 16
13 7
7 11
3 16
3 12
12 5
1 16
9 1
1 6
7 17
3 4
14 16
10 14
10 2
8 12
14 8
14 7
7 9
9 10
10 2
13 2
11 9
5 11
5 6
10 1
3 2
10 4
6 9 13 12
7 13 10 2
1 12 1 14
15 3 10 11
13 6 6 6
10 2 8 4
3 12 4 12
11 2 14 5
4 1 15 14
17 12 15 6
16 1 3 13
3 9 4 13
4 13 17 10
1 13 4 14
3 ...

output:

-1
-1
2
1
-1
-1
-1
1
1
2
2
2
-1
2
2
-1
2
-1
2
2
1
2
-1
-1
-1
1
-1
2
-1
-1

result:

ok 30 numbers

Test #16:

score: 0
Accepted
time: 4ms
memory: 87900kb

input:

18 15 30
6 4
6 11
11 12
18 12
18 9
16 9
16 3
12 14
14 10
1 12
6 2
1 17
8 12
8 15
5 15
13 8
12 7
3 9
12 9
12 1
1 8
8 2
2 14
11 14
6 11
5 2
8 13
10 13
13 7
4 7
15 12
3 3 13 5
15 9 2 7
4 9 7 3
3 11 15 12
1 5 8 15
2 5 14 4
18 6 5 8
15 3 7 15
9 1 17 3
1 13 12 14
5 8 8 5
14 6 11 12
5 14 11 5
12 4 11 14
13...

output:

1
1
-1
-1
-1
-1
1
1
-1
2
1
2
2
2
-1
-1
-1
2
-1
-1
1
-1
2
1
-1
2
-1
-1
-1
-1

result:

ok 30 numbers

Test #17:

score: 0
Accepted
time: 4ms
memory: 100204kb

input:

40 21 50
27 28
27 15
3 15
10 3
22 10
17 22
2 17
2 18
35 18
35 12
12 16
16 40
5 40
5 37
37 9
11 9
7 11
7 32
21 32
14 21
14 4
16 26
26 1
34 1
21 36
9 29
29 33
33 30
25 30
12 6
6 31
31 13
13 19
23 2
23 20
8 20
8 38
38 24
39 37
3 2
3 4
4 20
1 20
12 1
8 12
21 8
15 21
5 15
5 19
19 7
12 9
11 9
11 14
12 6
6...

output:

2
-1
2
-1
1
-1
1
2
2
-1
2
2
1
-1
2
2
-1
-1
1
-1
-1
-1
2
-1
-1
2
-1
2
-1
3
2
-1
2
-1
2
2
2
-1
2
-1
3
2
-1
2
-1
-1
2
2
-1
2

result:

ok 50 numbers

Test #18:

score: 0
Accepted
time: 0ms
memory: 100220kb

input:

30 22 50
30 18
29 18
29 24
24 27
27 3
3 23
5 23
4 5
21 4
26 21
13 26
28 5
20 28
3 11
12 11
22 12
3 1
1 8
8 14
14 17
7 17
25 4
16 25
9 16
18 15
2 3
2 10
3 19
19 6
11 7
7 9
9 20
8 20
8 10
10 16
17 16
17 12
15 12
21 15
21 2
18 2
18 22
6 22
16 4
4 13
19 15
14 19
3 14
3 1
1 5
18 18 21 10
8 4 7 12
18 12 8...

output:

-1
1
2
2
-1
-1
1
2
-1
-1
-1
-1
2
2
2
2
-1
2
-1
-1
-1
-1
-1
2
-1
2
2
-1
2
-1
-1
2
-1
-1
-1
2
-1
2
1
1
1
-1
-1
2
2
-1
2
-1
2
-1

result:

ok 50 numbers

Test #19:

score: 0
Accepted
time: 4ms
memory: 100192kb

input:

70 40 90
10 23
67 23
11 67
11 20
45 20
45 14
14 57
57 51
59 51
59 70
70 56
62 11
62 69
28 69
59 54
45 8
35 57
35 52
2 52
6 2
53 20
53 40
53 60
60 41
41 4
11 31
31 9
9 68
32 20
14 49
8 13
11 3
39 49
48 39
48 1
32 19
58 45
66 58
66 34
34 21
8 17
14 5
50 20
37 19
20 44
32 27
58 24
20 33
33 38
18 38
33 ...

output:

1
-1
-1
2
2
-1
2
-1
-1
-1
2
-1
1
-1
1
2
2
2
-1
2
-1
-1
-1
-1
-1
2
2
2
2
1
-1
-1
1
-1
1
2
2
2
-1
2
2
-1
-1
-1
1
2
2
-1
2
-1
-1
2
-1
2
-1
2
-1
2
-1
-1
2
-1
2
2
-1
2
1
2
-1
-1
1
2
1
2
-1
1
-1
2
2
-1
2
1
1
-1
-1
2
1
2
-1
-1

result:

ok 90 numbers

Test #20:

score: 0
Accepted
time: 4ms
memory: 104256kb

input:

70 50 90
45 67
45 5
56 5
45 65
5 53
45 55
5 51
45 19
5 9
5 42
52 45
45 38
5 3
5 54
10 5
5 15
45 6
45 31
26 5
5 33
16 5
18 45
5 37
4 5
25 5
45 43
60 5
59 45
8 5
45 21
39 45
32 45
69 5
11 45
13 45
45 44
5 48
45 17
28 5
5 34
5 62
45 57
45 50
5 64
5 1
5 46
45 66
45 2
45 68
27 45
45 7
29 5
45 49
45 30
63...

output:

1
1
1
-1
-1
-1
-1
1
1
1
1
-1
-1
-1
1
1
-1
1
1
-1
1
1
-1
1
-1
1
1
-1
-1
-1
1
-1
-1
-1
-1
1
1
-1
1
-1
1
-1
1
1
1
-1
-1
1
1
-1
1
-1
1
-1
1
-1
-1
-1
1
-1
1
-1
1
1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
1
-1
1
1
1
-1
1

result:

ok 90 numbers

Test #21:

score: 0
Accepted
time: 0ms
memory: 96172kb

input:

79 81 90
51 64
42 64
70 42
3 70
34 42
42 7
7 74
64 37
64 49
2 42
43 2
42 41
41 36
13 42
64 61
6 41
16 41
42 58
41 31
13 59
42 66
66 62
56 7
13 26
18 64
21 41
57 13
13 72
9 70
66 23
2 60
35 2
13 65
54 42
54 48
42 76
77 58
64 30
10 41
2 33
70 14
64 53
2 15
8 64
13 5
41 12
24 58
1 7
64 69
42 38
63 38
2...

output:

2
1
-1
2
1
2
2
2
2
-1
-1
1
-1
2
-1
2
-1
-1
1
2
2
2
2
-1
1
-1
-1
2
-1
-1
-1
2
-1
2
2
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
1
-1
2
1
2
-1
2
-1
-1
-1
2
2
2
-1
2
1
2
-1
-1
-1
1
-1
-1
-1
-1
2
2
-1
2
2
1
-1
-1
2
1
1
-1
1
-1
2
2
-1
-1
-1

result:

ok 90 numbers

Test #22:

score: 0
Accepted
time: 0ms
memory: 96108kb

input:

79 81 90
58 9
58 7
56 7
58 4
33 7
58 25
58 38
73 7
7 13
23 58
64 58
41 7
7 15
7 66
7 21
70 58
59 7
58 65
7 31
46 58
1 7
8 58
19 58
77 7
58 69
34 7
58 47
58 75
58 54
7 60
58 16
7 29
37 7
79 58
68 58
58 48
7 18
10 7
42 7
76 58
58 24
53 58
72 58
58 17
7 67
3 7
63 7
58 49
58 45
58 32
58 57
58 11
7 30
58...

output:

2
1
1
-1
-1
2
2
-1
1
-1
1
1
2
2
-1
-1
-1
-1
-1
1
-1
2
-1
1
2
1
2
-1
-1
-1
1
-1
-1
1
-1
-1
-1
2
1
1
1
2
2
-1
2
2
1
-1
2
2
-1
2
1
-1
1
-1
2
-1
-1
-1
-1
2
1
-1
2
-1
2
1
-1
2
1
-1
-1
1
2
2
-1
-1
-1
-1
1
2
-1
2
1
-1
-1
2
-1
2

result:

ok 90 numbers

Test #23:

score: 0
Accepted
time: 0ms
memory: 96124kb

input:

79 81 99
49 71
76 49
76 41
72 41
72 75
1 75
5 1
50 5
50 46
46 66
1 47
47 57
1 74
75 35
60 35
60 10
44 10
44 36
27 35
4 27
4 16
16 73
47 12
12 29
67 29
41 69
14 69
14 54
1 39
39 61
59 61
34 59
30 75
30 18
18 17
31 17
31 32
41 65
75 28
28 15
15 19
19 25
78 35
3 78
68 74
26 68
45 35
45 64
63 64
63 22
6...

output:

4
3
-1
-1
-1
1
2
3
-1
2
3
3
2
-1
2
-1
3
3
-1
3
2
-1
-1
2
4
-1
-1
3
1
2
2
2
2
3
-1
-1
3
2
-1
2
3
-1
3
-1
3
-1
3
-1
3
2
2
-1
3
-1
2
-1
2
-1
-1
3
-1
2
-1
3
1
3
2
-1
-1
2
2
1
2
2
3
3
-1
-1
-1
2
2
2
2
2
4
-1
2
-1
-1
-1
-1
-1
3
-1
-1
-1
4
-1
3

result:

ok 99 numbers

Test #24:

score: 0
Accepted
time: 7ms
memory: 104244kb

input:

79 81 99
23 53
19 53
36 19
35 36
57 35
1 57
1 20
20 40
11 40
26 11
48 26
35 55
20 59
68 59
68 2
57 69
69 12
46 12
54 57
54 52
1 9
47 9
62 47
62 15
15 34
40 73
73 13
13 27
73 41
73 49
16 54
16 70
70 50
47 39
28 1
77 28
38 77
16 64
64 43
43 44
16 75
75 37
67 53
79 35
60 79
60 72
30 77
30 29
19 6
14 57...

output:

-1
-1
2
2
-1
2
2
1
-1
-1
2
-1
-1
1
-1
2
2
-1
2
2
2
2
1
2
1
-1
-1
2
2
-1
-1
2
2
-1
-1
-1
2
-1
2
-1
2
-1
1
2
-1
-1
1
1
-1
-1
-1
2
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
1
2
-1
-1
-1
-1
2
-1
-1
-1
-1
1
2
-1
-1
2
2
-1
-1
2
-1
-1
-1
-1
2
2
-1
-1
-1
2
-1
-1
2
-1
2

result:

ok 99 numbers

Test #25:

score: 0
Accepted
time: 0ms
memory: 87924kb

input:

90 89 99
48 81
85 48
85 87
87 8
8 68
53 68
83 53
65 83
79 65
79 43
43 58
67 58
67 82
33 82
33 64
5 64
10 5
14 10
79 88
35 88
78 35
57 78
61 57
44 61
44 32
12 32
18 12
1 8
34 1
35 26
6 26
13 6
77 13
55 77
40 55
59 79
28 59
90 28
29 90
15 29
8 54
22 67
3 22
3 51
51 62
4 62
71 88
46 71
46 45
30 45
41 3...

output:

2
2
-1
-1
2
-1
-1
2
2
2
2
2
-1
-1
2
-1
2
2
-1
1
2
-1
2
-1
2
2
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
2
2
-1
2
-1
-1
2
2
-1
2
-1
1
-1
-1
-1
-1
2
2
2
-1
-1
-1
-1
2
1
-1
-1
-1
2
-1
-1
2
-1
2
-1
-1
2
2
-1
-1
-1
-1
2
-1
-1
2
-1
2
2
2
2
2
-1
2
2
2
2
-1
-1

result:

ok 99 numbers

Test #26:

score: 0
Accepted
time: 11ms
memory: 108500kb

input:

1000 2000 1000
55 910
869 55
548 869
155 548
155 72
72 556
556 558
558 1000
432 1000
338 432
676 338
669 676
669 52
52 279
874 279
77 874
367 77
367 625
611 625
611 549
812 549
333 812
114 333
114 400
400 420
731 420
731 898
898 372
372 127
318 127
318 33
936 33
936 859
198 859
198 663
663 46
596 46...

output:

4
-1
-1
7
-1
9
-1
-1
4
5
-1
8
11
10
6
14
7
-1
-1
3
-1
5
-1
8
6
-1
-1
4
4
-1
-1
9
7
5
-1
-1
-1
-1
-1
-1
-1
-1
8
-1
-1
-1
-1
8
-1
11
-1
-1
4
9
3
7
-1
10
-1
3
7
6
-1
6
-1
5
8
-1
-1
8
-1
7
-1
-1
5
-1
-1
9
-1
-1
12
-1
8
9
12
-1
9
-1
2
-1
-1
6
2
7
13
5
-1
10
6
11
-1
-1
11
-1
-1
8
4
-1
10
-1
-1
5
-1
-1
2
-...

result:

ok 1000 numbers

Test #27:

score: 0
Accepted
time: 8ms
memory: 122948kb

input:

4001 2000 2000
1288 2875
2703 1288
2703 65
1453 65
1453 1733
1733 580
580 22
22 1056
1568 1056
1568 2458
2458 2935
2935 197
197 2140
3941 2140
3399 3941
3399 3338
1934 3338
1934 481
1484 481
554 1484
554 708
1629 708
1216 1629
3785 1216
3785 3948
3948 1468
101 1468
1192 101
1143 1192
2608 1143
2608 ...

output:

5
-1
7
-1
7
-1
-1
10
-1
6
-1
2
13
3
3
-1
-1
7
5
-1
11
6
-1
-1
8
-1
-1
-1
2
5
-1
7
7
-1
11
-1
5
6
-1
-1
5
8
-1
9
11
-1
-1
-1
4
-1
6
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
9
-1
5
7
-1
3
-1
5
-1
8
-1
5
-1
4
-1
9
-1
-1
6
-1
10
-1
-1
-1
6
7
-1
-1
4
-1
4
-1
-1
5
-1
-1
6
-1
5
4
-1
-1
-1
4
-1
9
4
4
-1
-1
-1
5
-1
...

result:

ok 2000 numbers

Test #28:

score: -100
Wrong Answer
time: 16ms
memory: 121164kb

input:

9001 5000 5000
6459 5917
4454 5917
457 4454
457 5629
3359 5629
3359 2940
2940 3531
3531 8220
179 8220
179 8764
2671 8764
2671 5043
5043 3508
3508 2688
2688 1240
1240 3114
5296 3114
7431 5296
8727 7431
1696 8727
7040 1696
7040 8364
8364 6921
6921 7150
7150 2063
4749 2063
4749 6142
6142 5847
5847 7101...

output:

2
-1
-1
2
2
-1
3
-1
3
-1
4
-1
-1
-1
2
-1
-1
3
-1
-1
-1
2
4
-1
-1
-1
-1
3
3
4
-1
3
-1
-1
3
-1
2
2
2
-1
-1
4
3
2
-1
3
2
3
-1
4
-1
2
-1
-1
3
-1
3
2
-1
-1
3
-1
3
-1
-1
-1
-1
-1
3
-1
3
4
-1
-1
-1
2
-1
-1
-1
-1
-1
4
4
-1
-1
4
2
4
-1
-1
2
2
-1
-1
-1
-1
-1
3
-1
2
3
3
-1
3
3
2
-1
-1
3
4
-1
-1
3
2
4
3
2
2
2
2...

result:

wrong answer 193rd numbers differ - expected: '2', found: '3'