QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562632#9295. Treeshopzjy0001WA 7ms117068kbC++1710.5kb2024-09-13 19:36:422024-09-13 19:36:43

Judging History

This is the latest submission verdict.

  • [2024-09-13 19:36:43]
  • Judged
  • Verdict: WA
  • Time: 7ms
  • Memory: 117068kb
  • [2024-09-13 19:36:42]
  • 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(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
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 85940kb

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: 40820kb

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: 96092kb

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: 0ms
memory: 100280kb

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: 3ms
memory: 94012kb

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: 40880kb

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: 3ms
memory: 40752kb

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: 40756kb

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: 4ms
memory: 92016kb

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: 0ms
memory: 96044kb

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: 87920kb

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: 0ms
memory: 94120kb

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: 87984kb

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: 3ms
memory: 98096kb

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: 87980kb

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: 3ms
memory: 87928kb

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: 0ms
memory: 100268kb

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: 3ms
memory: 100208kb

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: 0ms
memory: 100268kb

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: 3ms
memory: 106352kb

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: 100124kb

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: 98176kb

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: 96056kb

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: 4ms
memory: 106356kb

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: 87880kb

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: 3ms
memory: 108496kb

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: 0ms
memory: 116736kb

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: 7ms
memory: 117068kb

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 192nd numbers differ - expected: '4', found: '3'