QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562542#9295. Treeshopzjy0001WA 8ms100400kbC++177.9kb2024-09-13 18:25:142024-09-13 18:25:14

Judging History

This is the latest submission verdict.

  • [2024-09-13 18:25:14]
  • Judged
  • Verdict: WA
  • Time: 8ms
  • Memory: 100400kb
  • [2024-09-13 18:25:14]
  • 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];
    pair<int,int>dp[N];
    int sz[N],son[N],d[N],f[N],top[N],dL[N],dR[N],bl[N],rk[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){
        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].first=u;
        for(auto v:G[u])if(v!=fa){
            Dp1(v,u);
            auto [a,b]=dp[u];auto [c,d]=dp[v];
            if(c&&(!a||dist(a,u)<dist(c,u)))swap(a,c);
            if(d&&(!a||dist(a,u)<dist(d,u)))swap(a,d);
            if(c&&(!b||dist(b,u)<dist(c,u)))swap(b,c);
            if(d&&(!b||dist(b,u)<dist(d,u)))swap(b,d);
            if(d&&(!c||dist(c,u)<dist(d,u)))swap(c,d);
            dp[u].first=a;
            if(b&&bl[a]!=bl[b])dp[u].second=b;
            else if(c&&bl[a]!=bl[c])dp[u].second=c;
            else if(d&&bl[a]!=bl[d])dp[u].second=d;
        }
    }
    inline void Dp2(int u,int fa){
        for(auto v:G[u])if(v!=fa){
            auto [a,b]=dp[u];auto [c,d]=dp[v];
            if(c&&(!a||dist(a,v)<dist(c,v)))swap(a,c);
            if(d&&(!a||dist(a,v)<dist(d,v)))swap(a,d);
            if(c&&(!b||dist(b,v)<dist(c,v)))swap(b,c);
            if(d&&(!b||dist(b,v)<dist(d,v)))swap(b,d);
            if(d&&(!c||dist(c,v)<dist(d,v)))swap(c,d);
            dp[v].first=a;
            if(b&&bl[a]!=bl[b])dp[v].second=b;
            else if(c&&bl[a]!=bl[c])dp[v].second=c;
            else if(d&&bl[a]!=bl[d])dp[v].second=d;
            Dp2(v,u);
        }
    }
    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)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;
        const auto [a,b]=dp[u];const auto [c,d]=dp[v];
        int sa=max(dist(u,a)+H.solve(a,v),H.solve(u,c)+dist(c,v)),sb=T.solve(u,v);
        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;
}
/*
20 15 1
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
9 1 14 4
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 75700kb

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: -100
Wrong Answer
time: 8ms
memory: 100400kb

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:

wrong answer 240th numbers differ - expected: '11', found: '12'