QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#431778#3501. Jailsnpmrnhlol100 ✓784ms88724kbC++148.4kb2024-06-06 05:09:212024-06-06 05:09:21

Judging History

你现在查看的是最新测评结果

  • [2024-06-06 05:09:21]
  • 评测
  • 测评结果:100
  • 用时:784ms
  • 内存:88724kb
  • [2024-06-06 05:09:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 12e4;
const int S = 5*N;
const int logN = 20;
int t;
vector <int> e[N];
vector <int> e2[S];
int deg[S];
int n,m;
int ls[S],rs[S];
queue <int> q;
int cnt = 0;
int root1;
int root2;
int sub[N];
int dpth[N];
int cnt2 = 0;
int st[N],st2[N];
int starts[N],endz[N];
int top[N];
int p1[N],p2[N];
int su[N],sw[N];
int pr[N];
int rmq[N][logN];
void build1(int l = 0,int r = n - 1,int node = 0){
    if(l != r){
        int mij = (l + r)/2;
        if(l != mij)ls[node] = cnt++;
        else ls[node] = p1[mij];
        if(mij + 1 != r)rs[node] = cnt++;
        else rs[node] = p1[mij + 1];
        //cout<<"addedge:"<<node<<' '<<ls[node]<<'\n';
        //cout<<"addedge:"<<node<<' '<<rs[node]<<'\n';
        e2[node].push_back(ls[node]);
        e2[node].push_back(rs[node]);
        build1(l,mij,ls[node]);
        build1(mij + 1,r,rs[node]);
    }
}
void build2(int l = 0,int r = n - 1,int node = 0){
    if(l != r){
        int mij = (l + r)/2;
        if(l != mij)ls[node] = cnt++;
        else ls[node] = p2[mij];
        if(mij + 1 != r)rs[node] = cnt++;
        else rs[node] = p2[mij + 1];
        //cout<<"addedge:"<<ls[node]<<' '<<node<<'\n';
        //cout<<"addedge:"<<rs[node]<<' '<<node<<'\n';
        e2[ls[node]].push_back(node);
        e2[rs[node]].push_back(node);
        build2(l,mij,ls[node]);
        build2(mij + 1,r,rs[node]);
    }
}
void dfs(int node, int p){
    pr[node] = p;
    sub[node] = 1;
    if(p == -1)dpth[node] = 0;
    else dpth[node] = dpth[p] + 1;
    for(auto i:e[node]){
        if(i == p)continue;
        dfs(i, node);
        sub[node]+=sub[i];
    }
    int mxid = -1;
    for(int i = 0;i < e[node].size();i++){
        if(e[node][i] == p)continue;
        if(mxid == -1 || sub[e[node][mxid]] < sub[e[node][i]]){
            mxid = i;
        }
    }
    if(mxid != -1){
        swap(e[node][mxid],e[node][0]);
    }
    for(int i = 0;i < e[node].size();i++){
        if(e[node][i] == p){
            swap(e[node][i],e[node].back());
            e[node].pop_back();
            break;
        }
    }
}
int last[N],first[N];
int laen[N],firen[N];
int rp1[N],rp2[N];
int cnt3 = 0,cnt4 = 0;
void dfs2(int node, int p){
    //cout<<"dfs:"<<node<<' '<<p<<'\n';
    st[node] = cnt2++;
    st2[cnt2 - 1] = node;
    bool ok = 0;
    if(starts[node] != -1){
        //cout<<"assignment:"<<node<<'\n';
        rp1[node] = cnt3++;
        p1[cnt3 - 1] = starts[node];
    }
    if(endz[node] != -1){
        rp2[node] = cnt4++;
        p2[cnt4 - 1] = endz[node];
    }
    if(starts[node] != -1){
        first[node] = node;
    }else if(top[node] == node){
        first[node] = -1;
    }else{
        first[node] = first[p];
    }
    //cout<<node<<' '<<first[node]<<'\n';
    if(endz[node] != -1){
        firen[node] = node;
    }else if(top[node] == node){
        firen[node] = -1;
    }else{
        firen[node] = firen[p];
    }
    for(auto i:e[node]){
        if(i == p)continue;
        if(!ok){
            top[i] = top[node];
        }else{
            top[i] = i;
        }
        dfs2(i, node);
        ok = 1;
    }
    if(starts[node] != -1){
        last[node] = node;
    }else if(!e[node].empty()){
        last[node] = last[e[node][0]];
    }else{
        last[node] = -1;
    }
    if(endz[node] != -1){
        laen[node] = node;
    }else if(!e[node].empty()){
        laen[node] = laen[e[node][0]];
    }else{
        laen[node] = -1;
    }
}
void updstart(int ql,int qr,int id,int l = 0,int r = m - 1,int node = root1){
    assert(ql <= qr);
    if(ql <= l && r <= qr){
        e2[id].push_back(node);
        //cout<<"addedge:"<<id<<' '<<node<<'\n';
    }else{
        int mij = (l + r)/2;
        if(qr <= mij){
            updstart(ql,qr,id,l,mij,ls[node]);
        }else if(mij + 1 <= ql){
            updstart(ql,qr,id,mij + 1,r,rs[node]);
        }else{
            updstart(ql,qr,id,l,mij,ls[node]);
            updstart(ql,qr,id,mij + 1,r,rs[node]);
        }
    }
}
void updends(int ql,int qr,int id,int l = 0,int r = m - 1,int node = root2){
    assert(ql <= qr);
    if(ql <= l && r <= qr){
        e2[node].push_back(id);
        //cout<<"addedge:"<<node<<' '<<id<<'\n';
    }else{
        int mij = (l + r)/2;
        if(qr <= mij){
            updends(ql,qr,id,l,mij,ls[node]);
        }else if(mij + 1 <= ql){
            updends(ql,qr,id,mij + 1,r,rs[node]);
        }else{
            updends(ql,qr,id,l,mij,ls[node]);
            updends(ql,qr,id,mij + 1,r,rs[node]);
        }
    }
}
int prog(int u,int w){
    int df = dpth[w] - dpth[u] - 1;
    if(df < 0)return pr[u];
    for(int i = logN - 1;i >= 0;i--){
        if(df>>i&1){
            df-=(1<<i);
            w = rmq[w][i];
        }
    }
    if(pr[w] == u)return w;
    return pr[u];
}
void addstarts(int u,int w,int id){
    u = prog(u,w);
    while(top[u] != top[w]){
        if(dpth[top[u]] > dpth[top[w]])swap(u,w);
        //cout<<"fire:"<<u<<' '<<w<<' '<<id<<' '<<first[w]<<' '<<last[top[w]]<<' '<<rp1[first[w]]<<' '<<rp1[last[top[w]]]<<'\n';
        if(first[w] != -1 && last[top[w]] != -1 && rp1[last[top[w]]] <= rp1[first[w]]){
            //cout<<first[w]<<' '<<last[top[w]]<<' '<<id<<'\n';
            updstart(rp1[last[top[w]]],rp1[first[w]],id);
        }
        w = pr[top[w]];
    }
    if(dpth[u] > dpth[w])swap(u,w);
    if(first[w] != -1 && last[u] != -1 && rp1[last[u]] <= rp1[first[w]]){
        //cout<<last[u]<<' '<<first[w]<<' '<<id<<'\n';
        updstart(rp1[last[u]],rp1[first[w]],id);
    }
}
void addends(int u,int w,int id){
    w = prog(w,u);
    while(top[u] != top[w]){
        if(dpth[top[u]] > dpth[top[w]])swap(u,w);
        if(firen[w] != -1 && laen[top[w]] != -1 && rp2[laen[top[w]]] <= rp2[firen[w]]){
            //cout<<firen[w]<<' '<<laen[top[w]]<<' '<<id<<"end\n";
            updends(rp2[laen[top[w]]],rp2[firen[w]],id);
        }
        w = pr[top[w]];
    }
    if(dpth[u] > dpth[w])swap(u,w);
    if(firen[w] != -1 && laen[u] != -1 && rp2[laen[u]] <= rp2[firen[w]]){
        //cout<<laen[u]<<' '<<firen[w]<<' '<<id<<"end\n";
        updends(rp2[laen[u]],rp2[firen[w]],id);
    }
}
bool topsort(){
    int nr = 0;
    for(int i = 0;i < cnt;i++){
        deg[i] = 0;
    }
    for(int i = 0;i < cnt;i++){
        for(auto j:e2[i]){
            deg[j]++;
        }
    }
    for(int i = 0;i < cnt;i++){
        if(deg[i] == 0)q.push(i);
    }
    while(!q.empty()){
        int x = q.front();
        nr++;
        q.pop();
        for(auto i:e2[x]){
            deg[i]--;
            if(deg[i] == 0){
                q.push(i);
            }
        }
    }
    return nr == cnt;
}
vector <pair<int,int>> dbg;
void solve(){
    cnt3 = cnt4 = 0;
    cin>>n;
    for(int i = 0;i < n - 1;i++){
        int u,w;
        cin>>u>>w;
        u--;w--;
        e[w].push_back(u);
        e[u].push_back(w);
    }
    for(int i = 0;i < n;i++){
        starts[i] = -1;
        endz[i] = -1;
    }
    cin>>m;
    for(int i = 0;i < m;i++){
        int u,w;
        cin>>u>>w;
        u--;w--;
        starts[u] = i;
        endz[w] = i;
        su[i] = u;
        sw[i] = w;
    }
    cnt2 = 0;
    top[0] = 0;
    dfs(0, -1);
    dfs2(0, -1);
    cnt = m;
    root1 = cnt++;
    build1(0,m - 1,cnt - 1);
    root2 = cnt++;
    build2(0,m - 1,cnt - 1);
    /*for(int i = 0;i < n;i++){
        for(auto j:e2[i]){
            cout<<"edge:"<<i<<' '<<j<<'\n';
        }
    }*/
    for(int i = 0;i < n;i++){
        rmq[i][0] = pr[i];
        //cout<<first[i]<<' '<<last[i]<<' '<<i<<' '<<top[i]<<'\n';
    }
    for(int j = 1;j < logN;j++){
        for(int i = 0;i < n;i++){
            rmq[i][j] = rmq[rmq[i][j - 1]][j - 1];
        }
    }
    for(int i = 0;i < m;i++){
        int u = su[i];
        int w = sw[i];
        addstarts(u,w,i);
        addends(u,w,i);
    }
    bool ok = topsort();
    if(ok){
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
    for(int i = 0;i < n;i++){
        e[i].clear();
    }
    for(int i = 0;i < cnt;i++){
        e2[i].clear();
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
/**
1
12
1 2
1 3
3 4
4 5
5 6
7 8
7 9
9 10
10 11
11 12
1 7
6
1 8
2 11
3 12
4 9
5 10
6 7
**/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 4ms
memory: 35940kb

input:

1
2
1 2
2
1 2
2 1

output:

No

result:

ok single line: 'No'

Test #2:

score: 5
Accepted
time: 11ms
memory: 36776kb

input:

462
120
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 ...

output:

No
Yes
Yes
No
Yes
No
Yes
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
No
No
Yes
No
No
No
No
No
No
No
Yes
Yes
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes
No
No
Yes
No
No
Yes
No
No
Yes
No
No
Yes
No
No
No
Ye...

result:

ok 462 lines

Test #3:

score: 5
Accepted
time: 17ms
memory: 33832kb

input:

1000
120
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...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 1000 lines

Test #4:

score: 5
Accepted
time: 0ms
memory: 39032kb

input:

20
250
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 5...

output:

Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
No
No
No
Yes
No
No
No
Yes
No
No
Yes

result:

ok 20 lines

Test #5:

score: 5
Accepted
time: 0ms
memory: 33668kb

input:

20
250
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 5...

output:

Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes

result:

ok 20 lines

Test #6:

score: 5
Accepted
time: 0ms
memory: 37124kb

input:

20
250
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 5...

output:

Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes

result:

ok 20 lines

Test #7:

score: 5
Accepted
time: 21ms
memory: 34652kb

input:

20
6000
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 ...

output:

Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes

result:

ok 20 lines

Test #8:

score: 5
Accepted
time: 31ms
memory: 55528kb

input:

1
120000
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...

output:

Yes

result:

ok single line: 'Yes'

Test #9:

score: 5
Accepted
time: 8ms
memory: 36092kb

input:

1000
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
4
1 2
7 4
15 8
17 12
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
7
1 2
3 4
5 8
7 10
9 14
15 18
17 20
21
1 2
2 3
3 4
4 5
5 6
6 7...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 1000 lines

Test #10:

score: 5
Accepted
time: 24ms
memory: 37248kb

input:

1000
120
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...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
...

result:

ok 1000 lines

Test #11:

score: 5
Accepted
time: 72ms
memory: 65380kb

input:

1
120000
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...

output:

Yes

result:

ok single line: 'Yes'

Test #12:

score: 5
Accepted
time: 77ms
memory: 65488kb

input:

1
120000
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...

output:

No

result:

ok single line: 'No'

Test #13:

score: 5
Accepted
time: 150ms
memory: 70324kb

input:

1
120000
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...

output:

No

result:

ok single line: 'No'

Test #14:

score: 5
Accepted
time: 403ms
memory: 88724kb

input:

1
120000
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...

output:

No

result:

ok single line: 'No'

Test #15:

score: 5
Accepted
time: 62ms
memory: 67720kb

input:

1
120000
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...

output:

Yes

result:

ok single line: 'Yes'

Test #16:

score: 5
Accepted
time: 92ms
memory: 69800kb

input:

1
120000
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...

output:

Yes

result:

ok single line: 'Yes'

Test #17:

score: 5
Accepted
time: 64ms
memory: 69004kb

input:

1
120000
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...

output:

Yes

result:

ok single line: 'Yes'

Test #18:

score: 5
Accepted
time: 86ms
memory: 69020kb

input:

1
120000
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...

output:

No

result:

ok single line: 'No'

Test #19:

score: 5
Accepted
time: 99ms
memory: 72972kb

input:

1
120000
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...

output:

No

result:

ok single line: 'No'

Test #20:

score: 5
Accepted
time: 41ms
memory: 64056kb

input:

1
120000
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...

output:

No

result:

ok single line: 'No'

Subtask #2:

score: 5
Accepted

Test #21:

score: 5
Accepted
time: 9ms
memory: 35824kb

input:

20
250
1 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
3 23
1 24
24 25
25 26
5 26
1 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
7 42
2 43
43 44
44 45
45 46
4 46
2 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
12 55
2 56
56 57
57 58
58 59
59 ...

output:

No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
Yes
Yes

result:

ok 20 lines

Test #22:

score: 5
Accepted
time: 0ms
memory: 36004kb

input:

20
250
1 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
3 23
1 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
5 32
1 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
7 41
2 42
42 43
43 44
44 45
45 46
46 47
4 47
2 48
48 49
49 50
50 51
51 52
52 53
53 54
12 54
2 55
55 56
56 57
57 58
58 59
14 ...

output:

Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #23:

score: 5
Accepted
time: 0ms
memory: 38788kb

input:

20
250
1 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
3 24
1 25
25 26
26 27
27 28
28 29
29 30
30 31
5 31
1 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
7 39
2 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
4 48
2 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
56 57
57 58
12 58
2 59
59 ...

output:

Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No

result:

ok 20 lines

Test #24:

score: 5
Accepted
time: 2ms
memory: 37296kb

input:

20
250
1 15
15 16
16 17
17 18
18 19
19 20
3 20
1 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
5 31
1 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
7 49
2 50
50 51
51 52
52 53
53 54
54 55
55 56
56 57
57 58
4 58
2 59
59 60
60...

output:

No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #25:

score: 5
Accepted
time: 4ms
memory: 33420kb

input:

20
250
1 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
3 31
1 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
5 39
1 40
40 41
41 42
42 43
43 44
44 45
7 45
2 46
46 47
47 48
48 49
49 50
50 51
4 51
2 52
52 53
53 54
54 55
55 56
56 57
57 58
58 59
59 60
12...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #26:

score: 5
Accepted
time: 0ms
memory: 38520kb

input:

20
250
1 15
15 16
16 17
17 18
18 19
19 20
3 20
1 21
21 22
22 23
23 24
24 25
25 26
26 27
5 27
1 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
7 37
2 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
4 46
2 47
47 48
12 48
2 49
49 50
50 51
14 51
3 52
52 53
53 54
54 55
55 56
56 57
57 58
58 5...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #27:

score: 5
Accepted
time: 5ms
memory: 35828kb

input:

20
250
1 15
15 16
16 17
17 18
18 19
19 20
20 21
3 21
1 22
22 23
23 24
24 25
5 25
1 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
7 39
2 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
4 47
2 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
12 56
2 57
57 58
58 59
59 ...

output:

Yes
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
Yes

result:

ok 20 lines

Test #28:

score: 5
Accepted
time: 4ms
memory: 37196kb

input:

17
250
1 15
15 16
16 17
17 18
18 19
19 20
20 21
3 21
1 22
22 23
23 24
24 25
25 26
26 27
27 28
5 28
1 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
7 39
2 40
40 41
41 42
4 42
2 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
12 54
2 55
55 56
56 57
57 58
58 59
59 ...

output:

Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 17 lines

Test #29:

score: 5
Accepted
time: 0ms
memory: 35912kb

input:

20
4
1 2
1 3
1 4
2
1 4
4 1
250
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 ...

output:

No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #30:

score: 5
Accepted
time: 9ms
memory: 37056kb

input:

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

output:

No
No
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes

result:

ok 20 lines

Subtask #3:

score: 16
Accepted

Dependency #2:

100%
Accepted

Test #31:

score: 16
Accepted
time: 0ms
memory: 36148kb

input:

20
250
1 2
1 3
3 4
2 5
4 6
6 7
1 8
6 9
8 10
7 11
4 12
11 13
8 14
14 15
1 16
15 17
17 18
11 19
2 20
13 21
2 22
2 23
12 24
14 25
22 26
23 27
12 28
17 29
22 30
30 31
14 32
10 33
5 34
15 35
26 36
10 37
21 38
22 39
2 40
31 41
20 42
22 43
43 44
26 45
36 46
5 47
10 48
45 49
15 50
34 51
49 52
15 53
3 54
28 ...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #32:

score: 16
Accepted
time: 8ms
memory: 33360kb

input:

20
250
1 2
2 3
3 4
2 5
3 6
5 7
6 8
8 9
9 10
9 11
9 12
9 13
13 14
12 15
13 16
13 17
15 18
15 19
19 20
17 21
21 22
19 23
21 24
21 25
23 26
25 27
26 28
26 29
28 30
30 31
28 32
29 33
32 34
32 35
32 36
35 37
35 38
37 39
37 40
38 41
39 42
40 43
41 44
43 45
45 46
45 47
44 48
48 49
47 50
47 51
50 52
49 53
5...

output:

Yes
No
No
No
Yes
No
No
Yes
No
No
Yes
No
No
No
Yes
Yes
No
Yes
No
No

result:

ok 20 lines

Test #33:

score: 16
Accepted
time: 0ms
memory: 35676kb

input:

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

output:

Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No

result:

ok 20 lines

Test #34:

score: 16
Accepted
time: 0ms
memory: 33524kb

input:

20
250
1 2
2 3
1 4
1 5
3 6
5 7
5 8
5 9
8 10
7 11
8 12
12 13
10 14
12 15
12 16
13 17
14 18
15 19
19 20
20 21
21 22
19 23
20 24
23 25
25 26
23 27
26 28
27 29
28 30
27 31
29 32
32 33
30 34
32 35
34 36
36 37
36 38
37 39
38 40
39 41
41 42
40 43
43 44
41 45
44 46
44 47
47 48
46 49
47 50
47 51
49 52
49 53
...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
No
No
Yes
Yes
No
No
Yes

result:

ok 20 lines

Test #35:

score: 16
Accepted
time: 10ms
memory: 38376kb

input:

20
250
1 2
2 3
2 4
4 5
3 6
6 7
6 8
6 9
9 10
9 11
9 12
12 13
11 14
12 15
15 16
14 17
17 18
18 19
17 20
18 21
19 22
21 23
21 24
22 25
25 26
26 27
26 28
28 29
29 30
28 31
30 32
32 33
31 34
32 35
34 36
34 37
35 38
36 39
38 40
40 41
41 42
41 43
42 44
44 45
43 46
44 47
47 48
48 49
49 50
48 51
50 52
52 53
...

output:

Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
No
Yes
No
Yes
No
No
No
Yes
No
Yes

result:

ok 20 lines

Test #36:

score: 16
Accepted
time: 4ms
memory: 36180kb

input:

20
250
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61
1...

output:

No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #37:

score: 16
Accepted
time: 0ms
memory: 36200kb

input:

20
12
1 2
2 3
2 4
4 5
1 6
7 8
8 9
8 10
10 11
7 12
1 7
6
1 12
2 11
3 10
4 9
5 8
6 7
12
1 2
1 3
1 4
1 5
1 6
7 8
7 9
7 10
7 11
7 12
1 7
6
1 8
2 7
3 9
4 12
5 11
6 10
12
1 2
2 3
1 4
1 5
4 6
7 8
8 9
7 10
7 11
10 12
1 7
6
1 9
2 8
3 11
4 10
5 12
6 7
12
1 2
2 3
2 4
2 5
1 6
7 8
8 9
8 10
8 11
7 12
1 7
6
1 9
2 ...

output:

Yes
Yes
Yes
Yes
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
Yes
No

result:

ok 20 lines

Test #38:

score: 16
Accepted
time: 4ms
memory: 33520kb

input:

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

output:

Yes
No
No
Yes
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes

result:

ok 20 lines

Test #39:

score: 16
Accepted
time: 0ms
memory: 35648kb

input:

20
246
114 183
25 82
127 221
7 59
176 220
155 244
15 67
52 230
191 222
92 127
81 103
13 61
103 110
75 80
126 141
135 187
60 192
79 151
118 147
61 188
134 173
125 147
216 236
40 62
177 212
112 133
105 198
131 205
146 168
135 167
202 231
200 232
88 209
131 176
104 159
116 245
136 223
13 91
80 134
105 ...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No

result:

ok 20 lines

Test #40:

score: 16
Accepted
time: 0ms
memory: 38568kb

input:

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

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes

result:

ok 20 lines

Test #41:

score: 16
Accepted
time: 8ms
memory: 33076kb

input:

20
250
1 2
1 3
2 4
4 5
3 6
1 7
2 8
1 9
9 10
9 11
11 12
12 13
9 14
14 15
11 16
4 17
11 18
9 19
10 20
15 21
16 22
4 23
17 24
6 25
2 26
19 27
14 28
21 29
13 30
14 31
21 32
21 33
31 34
3 35
5 36
19 37
27 38
6 39
3 40
12 41
33 42
25 43
13 44
40 45
28 46
25 47
37 48
31 49
40 50
45 51
28 52
16 53
37 54
2 5...

output:

No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #42:

score: 16
Accepted
time: 0ms
memory: 38424kb

input:

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

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok 20 lines

Subtask #4:

score: 28
Accepted

Dependency #3:

100%
Accepted

Test #43:

score: 28
Accepted
time: 0ms
memory: 33384kb

input:

20
250
1 2
2 3
3 4
1 5
1 6
1 7
7 8
1 9
3 10
5 11
11 12
10 13
9 14
2 15
14 16
8 17
6 18
9 19
12 20
10 21
13 22
2 23
15 24
5 25
1 26
9 27
21 28
12 29
13 30
9 31
31 32
25 33
27 34
15 35
2 36
17 37
5 38
36 39
16 40
4 41
28 42
7 43
28 44
5 45
11 46
36 47
29 48
13 49
28 50
35 51
51 52
24 53
35 54
23 55
42...

output:

No
No
No
Yes
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No

result:

ok 20 lines

Test #44:

score: 28
Accepted
time: 4ms
memory: 38336kb

input:

20
250
1 2
1 3
2 4
3 5
4 6
5 7
4 8
8 9
7 10
10 11
11 12
12 13
13 14
12 15
13 16
13 17
17 18
18 19
16 20
20 21
18 22
21 23
20 24
24 25
22 26
26 27
24 28
28 29
27 30
30 31
30 32
29 33
31 34
32 35
35 36
33 37
35 38
37 39
37 40
39 41
38 42
40 43
41 44
42 45
44 46
44 47
47 48
45 49
46 50
47 51
50 52
50 5...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok 20 lines

Test #45:

score: 28
Accepted
time: 4ms
memory: 37012kb

input:

20
250
1 2
1 3
2 4
2 5
3 6
3 7
7 8
6 9
6 10
7 11
8 12
9 13
11 14
13 15
12 16
14 17
15 18
16 19
18 20
17 21
19 22
20 23
23 24
21 25
24 26
24 27
26 28
27 29
26 30
27 31
29 32
29 33
33 34
32 35
34 36
35 37
37 38
37 39
39 40
37 41
38 42
39 43
40 44
43 45
45 46
46 47
44 48
46 49
47 50
48 51
50 52
50 53
5...

output:

No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
No
No
No
No
No
Yes
No

result:

ok 20 lines

Test #46:

score: 28
Accepted
time: 2ms
memory: 37104kb

input:

20
250
1 2
2 3
1 4
2 5
1 6
5 7
2 8
8 9
5 10
8 11
4 12
9 13
10 14
11 15
8 16
14 17
8 18
15 19
15 20
18 21
15 22
17 23
14 24
18 25
20 26
17 27
22 28
19 29
21 30
29 31
28 32
23 33
29 34
27 35
26 36
29 37
27 38
36 39
37 40
39 41
37 42
37 43
38 44
39 45
44 46
37 47
44 48
38 49
44 50
42 51
45 52
45 53
49 ...

output:

No
No
No
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
No
No
Yes
Yes
No
Yes
No
No

result:

ok 20 lines

Test #47:

score: 28
Accepted
time: 3ms
memory: 36044kb

input:

20
200
1 2
2 3
1 4
4 5
5 6
1 7
6 8
2 9
1 10
3 11
9 12
8 13
4 14
2 15
15 16
2 17
17 18
6 19
17 20
19 21
8 22
13 23
10 24
10 25
24 26
2 27
11 28
28 29
24 30
29 31
7 32
22 33
20 34
9 35
5 36
18 37
30 38
11 39
25 40
30 41
8 42
3 43
2 44
26 45
28 46
34 47
32 48
41 49
38 50
24 51
35 52
48 53
3 54
31 55
36...

output:

No
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
No
No
Yes
No
Yes

result:

ok 20 lines

Test #48:

score: 28
Accepted
time: 0ms
memory: 38696kb

input:

20
200
1 2
1 3
3 4
4 5
5 6
5 7
7 8
6 9
8 10
9 11
9 12
10 13
12 14
12 15
14 16
14 17
16 18
18 19
17 20
19 21
19 22
20 23
22 24
22 25
24 26
24 27
25 28
26 29
28 30
29 31
29 32
31 33
32 34
34 35
33 36
34 37
36 38
36 39
37 40
40 41
41 42
41 43
42 44
43 45
45 46
45 47
47 48
48 49
49 50
50 51
50 52
52 53
...

output:

No
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No

result:

ok 20 lines

Test #49:

score: 28
Accepted
time: 4ms
memory: 33448kb

input:

20
101
46 88
46 52
46 77
46 67
5 46
46 91
11 46
46 74
46 90
26 46
46 51
13 46
46 83
23 46
1 46
46 58
39 46
38 46
37 46
46 79
10 46
46 95
46 94
46 81
46 61
45 46
46 71
46 84
46 50
46 72
46 57
46 47
46 101
32 46
29 46
4 46
31 46
46 80
3 46
7 46
46 66
34 46
6 46
19 46
22 46
46 97
18 46
46 68
46 82
40 4...

output:

Yes
No
No
Yes
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No

result:

ok 20 lines

Test #50:

score: 28
Accepted
time: 0ms
memory: 36992kb

input:

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

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Subtask #5:

score: 12
Accepted

Dependency #4:

100%
Accepted

Test #51:

score: 12
Accepted
time: 32ms
memory: 33768kb

input:

20
6000
1 2
1 3
2 4
4 5
5 6
5 7
1 8
3 9
3 10
8 11
1 12
7 13
3 14
1 15
10 16
9 17
13 18
13 19
7 20
20 21
21 22
14 23
11 24
7 25
22 26
23 27
9 28
20 29
15 30
8 31
23 32
3 33
33 34
22 35
20 36
26 37
21 38
21 39
1 40
4 41
34 42
17 43
14 44
7 45
13 46
43 47
4 48
19 49
42 50
4 51
12 52
29 53
29 54
12 55
5...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No

result:

ok 20 lines

Test #52:

score: 12
Accepted
time: 23ms
memory: 39064kb

input:

20
6000
1 2
2 3
2 4
3 5
4 6
4 7
5 8
6 9
6 10
10 11
10 12
2 13
13 14
5 15
15 16
12 17
12 18
18 19
1 20
5 21
12 22
19 23
9 24
14 25
17 26
17 27
13 28
1 29
13 30
9 31
27 32
15 33
28 34
25 35
33 36
12 37
2 38
37 39
5 40
25 41
34 42
17 43
40 44
38 45
14 46
2 47
31 48
42 49
18 50
45 51
44 52
35 53
14 54
1...

output:

Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
No
No
Yes
No
Yes
Yes
Yes
No
Yes
Yes
Yes

result:

ok 20 lines

Test #53:

score: 12
Accepted
time: 23ms
memory: 34152kb

input:

20
6000
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61
...

output:

No
No
No
No
No
No
No
Yes
Yes
No
No
No
No
Yes
Yes
Yes
Yes
No
Yes
Yes

result:

ok 20 lines

Test #54:

score: 12
Accepted
time: 18ms
memory: 37412kb

input:

20
6000
1 2
2 3
3 4
4 5
2 6
5 7
5 8
6 9
6 10
9 11
10 12
12 13
10 14
14 15
15 16
13 17
15 18
15 19
19 20
17 21
21 22
19 23
23 24
23 25
22 26
26 27
25 28
26 29
29 30
28 31
29 32
30 33
30 34
32 35
32 36
36 37
37 38
38 39
36 40
37 41
40 42
39 43
43 44
43 45
45 46
43 47
46 48
47 49
47 50
50 51
48 52
50 5...

output:

Yes
Yes
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
Yes
No
No
No

result:

ok 20 lines

Test #55:

score: 12
Accepted
time: 6ms
memory: 36440kb

input:

20
1000
1 2
2 3
1 4
3 5
4 6
6 7
1 8
1 9
9 10
1 11
6 12
1 13
1 14
14 15
12 16
10 17
1 18
11 19
10 20
14 21
18 22
2 23
2 24
7 25
17 26
24 27
4 28
28 29
8 30
30 31
3 32
28 33
28 34
34 35
5 36
25 37
32 38
7 39
31 40
26 41
29 42
33 43
27 44
34 45
18 46
19 47
23 48
29 49
29 50
21 51
19 52
52 53
19 54
48 5...

output:

No
No
No
No
No
No
No
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No

result:

ok 20 lines

Test #56:

score: 12
Accepted
time: 34ms
memory: 46988kb

input:

1
120000
1 2
2 3
3 4
3 5
5 6
3 7
3 8
2 9
2 10
7 11
3 12
3 13
9 14
11 15
9 16
6 17
13 18
18 19
6 20
1 21
12 22
8 23
5 24
12 25
7 26
8 27
4 28
21 29
3 30
21 31
13 32
2 33
28 34
33 35
21 36
31 37
1 38
22 39
9 40
34 41
2 42
22 43
5 44
34 45
35 46
8 47
22 48
20 49
2 50
42 51
23 52
30 53
26 54
17 55
40 56...

output:

No

result:

ok single line: 'No'

Test #57:

score: 12
Accepted
time: 42ms
memory: 49088kb

input:

1
120000
1 2
2 3
2 4
4 5
3 6
1 7
5 8
4 9
5 10
4 11
9 12
12 13
5 14
9 15
10 16
1 17
10 18
3 19
5 20
8 21
9 22
12 23
17 24
9 25
2 26
19 27
1 28
12 29
6 30
20 31
3 32
9 33
12 34
27 35
27 36
20 37
16 38
6 39
29 40
24 41
26 42
26 43
22 44
13 45
11 46
24 47
23 48
7 49
37 50
44 51
27 52
14 53
27 54
25 55
5...

output:

Yes

result:

ok single line: 'Yes'

Test #58:

score: 12
Accepted
time: 35ms
memory: 53740kb

input:

1
120000
1 2
1 3
2 4
2 5
4 6
4 7
5 8
6 9
8 10
8 11
10 12
10 13
13 14
12 15
13 16
14 17
17 18
16 19
18 20
20 21
21 22
20 23
22 24
22 25
23 26
24 27
25 28
27 29
27 30
30 31
31 32
32 33
33 34
34 35
35 36
34 37
36 38
36 39
37 40
38 41
40 42
41 43
43 44
42 45
43 46
44 47
47 48
47 49
49 50
49 51
50 52
50 ...

output:

Yes

result:

ok single line: 'Yes'

Test #59:

score: 12
Accepted
time: 36ms
memory: 51636kb

input:

1
120000
1 2
1 3
2 4
2 5
3 6
6 7
5 8
6 9
9 10
9 11
10 12
11 13
13 14
13 15
15 16
15 17
15 18
18 19
18 20
20 21
19 22
22 23
23 24
23 25
25 26
26 27
25 28
28 29
27 30
29 31
29 32
32 33
31 34
34 35
33 36
36 37
35 38
36 39
38 40
38 41
40 42
42 43
43 44
44 45
45 46
45 47
46 48
46 49
49 50
49 51
50 52
50 ...

output:

Yes

result:

ok single line: 'Yes'

Test #60:

score: 12
Accepted
time: 36ms
memory: 49328kb

input:

1
120000
1 2
2 3
2 4
3 5
5 6
4 7
1 8
6 9
2 10
1 11
9 12
1 13
11 14
6 15
3 16
11 17
7 18
18 19
18 20
6 21
3 22
12 23
20 24
4 25
18 26
11 27
15 28
10 29
10 30
5 31
12 32
13 33
15 34
26 35
24 36
4 37
16 38
32 39
36 40
17 41
11 42
33 43
19 44
18 45
16 46
38 47
10 48
6 49
36 50
37 51
51 52
7 53
20 54
9 5...

output:

No

result:

ok single line: 'No'

Test #61:

score: 12
Accepted
time: 26ms
memory: 49200kb

input:

1
120000
1 2
1 3
3 4
1 5
5 6
4 7
6 8
3 9
1 10
9 11
10 12
3 13
13 14
4 15
3 16
16 17
7 18
6 19
18 20
3 21
10 22
15 23
7 24
14 25
24 26
20 27
27 28
13 29
2 30
29 31
28 32
20 33
31 34
24 35
33 36
30 37
35 38
1 39
23 40
32 41
31 42
37 43
34 44
7 45
2 46
25 47
39 48
10 49
36 50
50 51
1 52
40 53
9 54
19 5...

output:

Yes

result:

ok single line: 'Yes'

Test #62:

score: 12
Accepted
time: 33ms
memory: 50608kb

input:

1
120000
1 2
2 3
3 4
2 5
5 6
2 7
6 8
5 9
9 10
2 11
6 12
8 13
9 14
9 15
12 16
7 17
11 18
11 19
11 20
13 21
19 22
20 23
23 24
18 25
18 26
20 27
25 28
24 29
27 30
22 31
24 32
31 33
24 34
25 35
28 36
34 37
28 38
30 39
34 40
32 41
38 42
33 43
39 44
40 45
41 46
44 47
43 48
43 49
42 50
42 51
42 52
45 53
47...

output:

Yes

result:

ok single line: 'Yes'

Test #63:

score: 12
Accepted
time: 32ms
memory: 48652kb

input:

1
120000
1 2
2 3
2 4
4 5
1 6
6 7
3 8
1 9
2 10
5 11
8 12
12 13
5 14
8 15
14 16
15 17
7 18
18 19
14 20
10 21
12 22
22 23
23 24
24 25
23 26
24 27
25 28
27 29
20 30
24 31
30 32
23 33
24 34
34 35
31 36
34 37
36 38
38 39
31 40
33 41
38 42
35 43
37 44
39 45
38 46
41 47
37 48
39 49
48 50
43 51
47 52
51 53
4...

output:

No

result:

ok single line: 'No'

Test #64:

score: 12
Accepted
time: 12ms
memory: 38624kb

input:

20
501
190 352
328 352
288 352
304 352
9 352
307 352
352 385
352 499
221 352
309 352
137 352
223 352
142 352
8 352
270 352
229 352
265 352
228 352
218 352
19 352
259 352
199 352
267 352
344 352
85 352
166 352
156 352
99 352
352 489
281 352
121 352
83 352
14 352
352 384
352 455
352 403
186 352
330 35...

output:

Yes
No
No
Yes
No
Yes
No
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes

result:

ok 20 lines

Test #65:

score: 12
Accepted
time: 50ms
memory: 49084kb

input:

1
120000
9596 32034
82692 85993
30880 60468
22127 89935
44536 51056
29638 71986
57153 103961
11021 66919
65177 96684
4542 48982
10457 21422
10762 52690
76467 105536
31498 46755
48690 82310
13509 118283
15463 106906
7541 66632
74654 103950
58261 68753
15087 48231
31649 96398
69483 90580
36955 85619
2...

output:

Yes

result:

ok single line: 'Yes'

Subtask #6:

score: 11
Accepted

Test #66:

score: 11
Accepted
time: 21ms
memory: 33556kb

input:

1000
10
1 2
2 3
1 4
4 5
4 6
4 7
2 8
8 9
3 10
2
5 4
1 9
10
1 2
1 3
1 4
4 5
4 6
3 7
3 8
2 9
6 10
2
2 9
1 5
10
1 2
2 3
1 4
4 5
4 6
2 7
3 8
2 9
1 10
2
10 2
7 5
10
1 2
1 3
1 4
2 5
1 6
3 7
2 8
7 9
2 10
2
10 5
2 7
10
1 2
1 3
1 4
3 5
5 6
3 7
7 8
1 9
8 10
2
6 7
1 2
10
1 2
1 3
3 4
2 5
4 6
3 7
1 8
4 9
1 10
2
1...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
No
No
No
No
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
...

result:

ok 1000 lines

Test #67:

score: 11
Accepted
time: 26ms
memory: 36172kb

input:

1000
120
1 2
2 3
1 4
1 5
2 6
3 7
3 8
3 9
6 10
4 11
8 12
6 13
1 14
6 15
11 16
3 17
17 18
5 19
1 20
16 21
18 22
21 23
14 24
20 25
6 26
13 27
4 28
23 29
29 30
2 31
14 32
18 33
9 34
13 35
17 36
2 37
7 38
20 39
26 40
22 41
37 42
30 43
43 44
42 45
9 46
43 47
29 48
9 49
45 50
49 51
48 52
9 53
20 54
9 55
5 ...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Y...

result:

ok 1000 lines

Test #68:

score: 11
Accepted
time: 16ms
memory: 38556kb

input:

1000
120
1 2
2 3
1 4
1 5
3 6
1 7
7 8
2 9
1 10
5 11
5 12
7 13
4 14
11 15
10 16
15 17
10 18
1 19
18 20
8 21
14 22
4 23
8 24
9 25
5 26
20 27
9 28
11 29
19 30
8 31
6 32
30 33
2 34
14 35
30 36
3 37
11 38
17 39
14 40
39 41
18 42
36 43
37 44
29 45
32 46
42 47
29 48
16 49
3 50
47 51
16 52
3 53
36 54
24 55
5...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 1000 lines

Test #69:

score: 11
Accepted
time: 53ms
memory: 50224kb

input:

1
120000
1 2
1 3
3 4
4 5
1 6
5 7
7 8
4 9
7 10
4 11
7 12
10 13
5 14
6 15
15 16
3 17
15 18
1 19
10 20
2 21
18 22
16 23
12 24
23 25
2 26
12 27
8 28
5 29
12 30
30 31
23 32
7 33
16 34
25 35
5 36
8 37
19 38
6 39
30 40
4 41
33 42
27 43
43 44
27 45
44 46
22 47
26 48
29 49
29 50
28 51
9 52
20 53
41 54
1 55
4...

output:

No

result:

ok single line: 'No'

Test #70:

score: 11
Accepted
time: 196ms
memory: 58784kb

input:

1
120000
1 2
2 3
2 4
4 5
4 6
6 7
6 8
4 9
7 10
3 11
8 12
11 13
5 14
13 15
4 16
2 17
9 18
4 19
12 20
7 21
7 22
7 23
13 24
18 25
1 26
21 27
5 28
16 29
9 30
30 31
29 32
24 33
9 34
27 35
16 36
5 37
36 38
10 39
5 40
16 41
27 42
41 43
24 44
26 45
7 46
44 47
30 48
33 49
42 50
11 51
5 52
38 53
13 54
43 55
19...

output:

No

result:

ok single line: 'No'

Test #71:

score: 11
Accepted
time: 504ms
memory: 75332kb

input:

1
120000
1 2
1 3
2 4
3 5
3 6
2 7
3 8
4 9
5 10
2 11
3 12
9 13
12 14
1 15
13 16
2 17
11 18
10 19
14 20
1 21
20 22
8 23
9 24
20 25
13 26
13 27
19 28
10 29
26 30
4 31
25 32
28 33
30 34
26 35
35 36
17 37
21 38
28 39
39 40
1 41
26 42
26 43
26 44
42 45
44 46
23 47
11 48
29 49
32 50
10 51
25 52
50 53
36 54
...

output:

No

result:

ok single line: 'No'

Test #72:

score: 11
Accepted
time: 52ms
memory: 51136kb

input:

1
120000
1 2
2 3
2 4
2 5
5 6
5 7
1 8
2 9
9 10
9 11
3 12
11 13
4 14
3 15
5 16
10 17
17 18
6 19
13 20
7 21
2 22
11 23
13 24
18 25
23 26
6 27
22 28
24 29
2 30
24 31
30 32
6 33
16 34
31 35
30 36
31 37
6 38
38 39
32 40
19 41
41 42
31 43
39 44
40 45
45 46
7 47
11 48
8 49
49 50
6 51
38 52
17 53
28 54
12 55...

output:

Yes

result:

ok single line: 'Yes'

Test #73:

score: 11
Accepted
time: 55ms
memory: 51092kb

input:

1
120000
1 2
1 3
3 4
1 5
5 6
5 7
3 8
6 9
2 10
5 11
2 12
7 13
6 14
10 15
2 16
13 17
7 18
14 19
10 20
12 21
6 22
4 23
19 24
13 25
16 26
16 27
15 28
12 29
15 30
27 31
17 32
29 33
1 34
1 35
1 36
36 37
4 38
38 39
18 40
14 41
21 42
13 43
25 44
43 45
36 46
4 47
40 48
6 49
42 50
10 51
29 52
12 53
22 54
28 5...

output:

No

result:

ok single line: 'No'

Test #74:

score: 11
Accepted
time: 62ms
memory: 51316kb

input:

1
120000
1 2
2 3
1 4
1 5
4 6
6 7
5 8
1 9
5 10
9 11
1 12
8 13
10 14
6 15
15 16
13 17
1 18
11 19
9 20
7 21
4 22
5 23
4 24
12 25
18 26
17 27
1 28
23 29
11 30
18 31
27 32
19 33
21 34
19 35
23 36
1 37
32 38
38 39
27 40
36 41
41 42
30 43
39 44
34 45
18 46
34 47
28 48
35 49
2 50
43 51
17 52
4 53
41 54
41 5...

output:

Yes

result:

ok single line: 'Yes'

Test #75:

score: 11
Accepted
time: 168ms
memory: 58288kb

input:

1
120000
1 2
1 3
1 4
2 5
1 6
4 7
6 8
2 9
9 10
1 11
10 12
9 13
12 14
4 15
1 16
9 17
13 18
10 19
6 20
8 21
6 22
12 23
11 24
19 25
1 26
9 27
20 28
24 29
6 30
13 31
17 32
23 33
23 34
6 35
25 36
36 37
17 38
3 39
18 40
4 41
8 42
17 43
8 44
21 45
21 46
21 47
5 48
4 49
17 50
22 51
14 52
18 53
49 54
30 55
29...

output:

No

result:

ok single line: 'No'

Test #76:

score: 11
Accepted
time: 113ms
memory: 57512kb

input:

1
120000
1 2
2 3
2 4
2 5
3 6
1 7
6 8
3 9
9 10
2 11
1 12
8 13
7 14
13 15
3 16
4 17
14 18
9 19
15 20
4 21
19 22
5 23
20 24
12 25
9 26
20 27
3 28
20 29
4 30
18 31
10 32
32 33
17 34
25 35
19 36
28 37
8 38
10 39
7 40
6 41
24 42
21 43
25 44
37 45
23 46
32 47
36 48
40 49
46 50
30 51
9 52
31 53
27 54
1 55
2...

output:

No

result:

ok single line: 'No'

Test #77:

score: 11
Accepted
time: 134ms
memory: 57828kb

input:

1
120000
1 2
1 3
1 4
1 5
3 6
4 7
4 8
6 9
7 10
10 11
7 12
2 13
9 14
6 15
8 16
3 17
17 18
15 19
10 20
9 21
10 22
13 23
21 24
20 25
3 26
1 27
6 28
25 29
14 30
16 31
2 32
17 33
20 34
9 35
14 36
21 37
23 38
17 39
19 40
11 41
4 42
17 43
37 44
34 45
32 46
25 47
27 48
21 49
18 50
4 51
14 52
34 53
40 54
48 5...

output:

Yes

result:

ok single line: 'Yes'

Test #78:

score: 11
Accepted
time: 117ms
memory: 58084kb

input:

1
120000
1 2
2 3
3 4
3 5
5 6
1 7
4 8
3 9
8 10
9 11
6 12
9 13
8 14
5 15
8 16
10 17
13 18
18 19
6 20
18 21
5 22
16 23
1 24
24 25
7 26
20 27
18 28
27 29
20 30
10 31
6 32
14 33
8 34
6 35
34 36
23 37
14 38
9 39
19 40
32 41
26 42
3 43
3 44
6 45
29 46
21 47
20 48
32 49
33 50
29 51
49 52
41 53
44 54
20 55
8...

output:

No

result:

ok single line: 'No'

Test #79:

score: 11
Accepted
time: 123ms
memory: 57940kb

input:

1
120000
1 2
1 3
2 4
2 5
2 6
1 7
4 8
7 9
8 10
4 11
2 12
12 13
8 14
5 15
6 16
14 17
2 18
4 19
15 20
10 21
10 22
21 23
7 24
13 25
17 26
13 27
5 28
24 29
12 30
25 31
12 32
17 33
29 34
10 35
5 36
2 37
18 38
32 39
12 40
38 41
3 42
15 43
29 44
28 45
5 46
25 47
34 48
23 49
19 50
8 51
49 52
38 53
19 54
26 5...

output:

Yes

result:

ok single line: 'Yes'

Test #80:

score: 11
Accepted
time: 168ms
memory: 60448kb

input:

1
120000
11991 50256
11991 84876
11991 45905
11991 51568
11991 91200
11991 42928
11991 113754
8591 11991
11991 39222
11991 41683
11991 14143
11991 39036
11991 17920
11991 31807
11991 94372
11160 11991
11991 91065
11991 40582
11991 70878
11991 41750
11991 33677
11991 108658
11991 28168
11991 39793
11...

output:

Yes

result:

ok single line: 'Yes'

Test #81:

score: 11
Accepted
time: 178ms
memory: 60416kb

input:

1
120000
18188 106790
18188 54059
18188 89312
1977 18188
18188 28194
18188 65674
18188 101181
18188 24303
17901 18188
18188 89721
18188 73511
2884 18188
18188 77276
4949 18188
18188 24043
18188 39177
18188 112466
7926 18188
18188 71531
18188 35382
18188 19597
18188 88563
7163 18188
18188 117028
1818...

output:

No

result:

ok single line: 'No'

Test #82:

score: 11
Accepted
time: 156ms
memory: 60568kb

input:

1
120000
88901 93340
53582 88901
17631 88901
88901 112891
49610 88901
66056 88901
37119 88901
13628 88901
76827 88901
88901 113073
35676 88901
88901 119510
48422 88901
87908 88901
45477 88901
31754 88901
7989 88901
56079 88901
11230 88901
79317 88901
88901 118351
7557 88901
5525 88901
36133 88901
38...

output:

No

result:

ok single line: 'No'

Test #83:

score: 11
Accepted
time: 97ms
memory: 54772kb

input:

1
119999
25598 38818
90634 115889
12633 50464
69321 90502
61890 69321
50833 62180
44063 110322
56990 71717
69321 97043
9004 31721
72739 99897
70071 77183
1641 5950
11923 22839
85938 113668
44393 113227
57650 106543
62003 110244
2984 69321
69321 74070
31878 69321
53020 85766
21247 69321
9380 71862
26...

output:

Yes

result:

ok single line: 'Yes'

Test #84:

score: 11
Accepted
time: 88ms
memory: 54772kb

input:

1
119999
13044 22298
36898 57927
71259 116062
13044 72264
33247 118187
48341 93486
48634 70190
88330 108870
24718 65527
13044 13377
7808 77099
29483 111980
52095 97954
13044 28310
13044 88491
13044 73275
108092 110305
13044 76937
13044 55663
13044 39070
51360 65292
13044 109934
45068 89262
5748 1775...

output:

No

result:

ok single line: 'No'

Test #85:

score: 11
Accepted
time: 98ms
memory: 54988kb

input:

1
119999
35328 94869
90311 115735
74625 115735
73760 108911
7771 115735
104915 115735
21124 89210
103290 115735
115735 117754
87997 119165
55414 115735
65186 86428
29392 115735
47518 71428
115735 119115
106540 112998
7327 115735
41944 115735
37454 115735
30208 50594
8164 11521
42835 99431
101819 119...

output:

Yes

result:

ok single line: 'Yes'

Test #86:

score: 11
Accepted
time: 82ms
memory: 54772kb

input:

1
119999
41911 92600
40028 45987
45987 108241
60151 76109
45987 80553
45987 102943
17209 65161
19179 45987
45987 117820
45987 47874
75073 94327
31981 36446
22706 78045
5600 45987
18295 45987
45987 64839
4384 45987
45987 63427
59905 97176
45987 102843
45987 77142
32336 94133
6104 26212
27469 112582
4...

output:

No

result:

ok single line: 'No'

Subtask #7:

score: 23
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #87:

score: 23
Accepted
time: 24ms
memory: 36292kb

input:

1000
10
1 2
1 3
2 4
4 5
1 6
2 7
3 8
6 9
8 10
2
5 10
2 3
10
1 2
2 3
2 4
4 5
4 6
3 7
1 8
4 9
2 10
2
10 9
5 7
10
1 2
1 3
3 4
3 5
2 6
4 7
3 8
7 9
4 10
2
9 3
4 8
10
1 2
1 3
3 4
3 5
2 6
3 7
2 8
7 9
8 10
2
10 4
6 8
10
1 2
2 3
3 4
1 5
4 6
3 7
2 8
6 9
5 10
2
3 2
6 3
10
1 2
1 3
3 4
1 5
5 6
2 7
7 8
3 9
2 10
2
...

output:

No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
No
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
No
Yes
No
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Ye...

result:

ok 1000 lines

Test #88:

score: 23
Accepted
time: 11ms
memory: 33360kb

input:

800
120
1 2
1 3
2 4
4 5
3 6
3 7
4 8
5 9
9 10
10 11
10 12
9 13
10 14
11 15
12 16
13 17
17 18
17 19
18 20
17 21
21 22
22 23
21 24
23 25
23 26
25 27
27 28
28 29
29 30
29 31
31 32
31 33
32 34
34 35
35 36
34 37
35 38
38 39
38 40
39 41
40 42
41 43
42 44
43 45
45 46
44 47
45 48
45 49
48 50
48 51
51 52
49 5...

output:

No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No...

result:

ok 800 lines

Test #89:

score: 23
Accepted
time: 198ms
memory: 68260kb

input:

1
120000
1 2
1 3
1 4
4 5
4 6
6 7
7 8
8 9
9 10
9 11
10 12
11 13
13 14
14 15
15 16
16 17
15 18
16 19
19 20
18 21
19 22
20 23
22 24
24 25
25 26
24 27
27 28
28 29
27 30
29 31
30 32
30 33
32 34
34 35
34 36
36 37
37 38
38 39
38 40
38 41
41 42
40 43
43 44
42 45
44 46
44 47
47 48
47 49
48 50
49 51
51 52
52 ...

output:

No

result:

ok single line: 'No'

Test #90:

score: 23
Accepted
time: 53ms
memory: 55784kb

input:

1
120000
1 2
1 3
3 4
3 5
3 6
5 7
6 8
7 9
9 10
8 11
9 12
10 13
13 14
13 15
15 16
15 17
16 18
18 19
19 20
20 21
20 22
22 23
23 24
24 25
23 26
26 27
27 28
28 29
27 30
28 31
29 32
31 33
31 34
34 35
34 36
36 37
36 38
38 39
37 40
38 41
39 42
42 43
41 44
44 45
45 46
44 47
45 48
48 49
48 50
48 51
50 52
51 5...

output:

Yes

result:

ok single line: 'Yes'

Test #91:

score: 23
Accepted
time: 116ms
memory: 64104kb

input:

1
120000
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

No

result:

ok single line: 'No'

Test #92:

score: 23
Accepted
time: 19ms
memory: 47588kb

input:

1
120000
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 61...

output:

Yes

result:

ok single line: 'Yes'

Test #93:

score: 23
Accepted
time: 93ms
memory: 55312kb

input:

1
119999
70469 99143
16873 47858
9183 74783
23127 35608
20869 67057
13987 54887
32438 79640
7968 103514
90902 103871
972 57706
5598 21618
14192 66650
22858 68904
13024 58854
92846 95558
41561 69342
26765 58042
37250 88739
58169 95984
11676 60837
80130 92441
22650 46583
35536 95867
92019 112282
91195...

output:

Yes

result:

ok single line: 'Yes'

Test #94:

score: 23
Accepted
time: 784ms
memory: 86056kb

input:

1
120000
25156 34477
10715 65847
49587 115425
74758 115038
53099 68831
23261 42871
53891 76238
28706 43443
71501 106462
6685 79072
2017 98160
17209 107357
30856 82298
45194 87405
51195 86447
32653 49142
3693 74407
23546 69698
2422 90463
11872 56423
25292 76680
5861 48314
5276 64965
1271 90020
52018 ...

output:

No

result:

ok single line: 'No'

Test #95:

score: 23
Accepted
time: 47ms
memory: 46984kb

input:

1
120000
72239 107238
80278 100093
37710 82865
22639 77476
13945 63629
30079 60294
34114 87516
10776 72676
85909 94342
48342 69393
50019 69472
39250 116307
7938 67051
37189 113042
62668 119999
69448 102244
24902 98397
76326 97075
16290 102165
33593 58512
8127 26289
9224 72454
29503 101273
96765 1158...

output:

Yes

result:

ok single line: 'Yes'

Test #96:

score: 23
Accepted
time: 41ms
memory: 47016kb

input:

1
120000
74756 109551
71920 90535
54533 85191
38683 41935
31104 107478
58532 119063
47934 88396
34828 61337
30321 67341
14588 75823
18000 65835
86460 113918
9600 104309
11799 75533
86806 106416
22474 94346
19652 88883
39905 67299
23984 108622
75920 109621
45416 94615
45403 56730
58439 85962
32189 84...

output:

No

result:

ok single line: 'No'

Test #97:

score: 23
Accepted
time: 10ms
memory: 39092kb

input:

1
9999
185 9957
1715 5500
2519 7814
711 9809
7405 9558
204 9025
2893 3714
3530 6418
2788 5224
1709 7347
2058 9102
2221 3425
5850 8822
2665 4330
380 2193
1087 2550
5357 7777
3611 9375
3952 7528
872 6213
6173 6438
4343 5353
1913 6981
5054 6916
3070 6083
2802 7960
2827 4077
2349 7926
2133 6340
1708 977...

output:

Yes

result:

ok single line: 'Yes'

Test #98:

score: 23
Accepted
time: 126ms
memory: 56124kb

input:

1
119999
52081 90449
46374 87819
34295 60980
31405 64625
82099 112907
81592 106466
7995 65412
47309 88640
83549 99283
16691 90893
60307 66153
15241 40723
66830 98587
16764 59040
81169 110857
1963 72980
64470 74475
26658 94239
10310 55681
47199 74597
33307 92295
7807 79530
64608 106788
86239 108891
1...

output:

Yes

result:

ok single line: 'Yes'

Test #99:

score: 23
Accepted
time: 132ms
memory: 56152kb

input:

1
119999
21835 57213
83638 105517
103205 118280
41294 87811
63845 65718
51163 87281
14987 45604
8700 82563
66374 109916
892 55330
108327 117663
64744 113066
19173 55205
42014 93615
30220 85806
47252 47299
51529 63650
20090 46794
45388 95627
20136 96674
9518 65430
26929 90338
61915 85491
61820 111921...

output:

Yes

result:

ok single line: 'Yes'

Test #100:

score: 23
Accepted
time: 58ms
memory: 57724kb

input:

1
120000
1 2
2 3
2 4
4 5
5 6
5 7
6 8
7 9
9 10
9 11
10 12
12 13
13 14
14 15
14 16
15 17
16 18
17 19
19 20
19 21
21 22
21 23
23 24
24 25
24 26
25 27
27 28
28 29
29 30
30 31
31 32
32 33
32 34
33 35
35 36
36 37
36 38
37 39
38 40
39 41
41 42
42 43
43 44
44 45
44 46
45 47
47 48
48 49
49 50
49 51
50 52
51 ...

output:

Yes

result:

ok single line: 'Yes'

Test #101:

score: 23
Accepted
time: 63ms
memory: 59428kb

input:

1
120000
1 2
1 3
2 4
4 5
5 6
5 7
6 8
7 9
9 10
9 11
11 12
12 13
13 14
13 15
15 16
15 17
17 18
17 19
19 20
20 21
21 22
21 23
23 24
24 25
25 26
25 27
26 28
27 29
29 30
29 31
30 32
32 33
32 34
34 35
35 36
35 37
36 38
38 39
39 40
39 41
40 42
42 43
43 44
44 45
45 46
45 47
47 48
48 49
49 50
49 51
51 52
51 ...

output:

No

result:

ok single line: 'No'

Test #102:

score: 23
Accepted
time: 54ms
memory: 57868kb

input:

1
120000
1 2
1 3
2 4
3 5
4 6
5 7
6 8
8 9
9 10
9 11
10 12
11 13
13 14
14 15
14 16
16 17
16 18
18 19
19 20
19 21
20 22
22 23
23 24
24 25
24 26
25 27
26 28
28 29
28 30
29 31
31 32
31 33
33 34
33 35
35 36
36 37
37 38
38 39
39 40
39 41
40 42
42 43
43 44
44 45
44 46
46 47
46 48
47 49
48 50
50 51
51 52
52 ...

output:

No

result:

ok single line: 'No'

Test #103:

score: 23
Accepted
time: 453ms
memory: 85952kb

input:

1
120000
1 2
2 3
2 4
4 5
4 6
6 7
7 8
7 9
8 10
9 11
11 12
12 13
13 14
13 15
14 16
16 17
16 18
18 19
18 20
19 21
21 22
22 23
23 24
23 25
25 26
26 27
26 28
27 29
29 30
30 31
31 32
32 33
33 34
34 35
34 36
36 37
36 38
38 39
39 40
40 41
40 42
41 43
43 44
43 45
44 46
45 47
47 48
48 49
49 50
50 51
51 52
51 ...

output:

No

result:

ok single line: 'No'

Test #104:

score: 23
Accepted
time: 132ms
memory: 67292kb

input:

1
120000
1 2
1 3
3 4
3 5
5 6
6 7
6 8
8 9
8 10
9 11
11 12
11 13
12 14
14 15
14 16
15 17
17 18
18 19
19 20
19 21
21 22
22 23
23 24
23 25
25 26
26 27
27 28
27 29
29 30
29 31
31 32
31 33
32 34
33 35
34 36
35 37
37 38
37 39
39 40
39 41
40 42
42 43
43 44
43 45
44 46
46 47
47 48
47 49
49 50
49 51
50 52
51 ...

output:

No

result:

ok single line: 'No'

Test #105:

score: 23
Accepted
time: 77ms
memory: 66984kb

input:

1
120000
1 2
2 3
2 4
4 5
5 6
6 7
7 8
7 9
8 10
9 11
10 12
11 13
12 14
14 15
15 16
16 17
17 18
18 19
18 20
19 21
21 22
21 23
22 24
24 25
25 26
25 27
27 28
28 29
28 30
30 31
30 32
31 33
32 34
33 35
35 36
36 37
36 38
38 39
39 40
40 41
41 42
42 43
42 44
44 45
44 46
46 47
47 48
47 49
49 50
49 51
51 52
51 ...

output:

No

result:

ok single line: 'No'

Test #106:

score: 23
Accepted
time: 79ms
memory: 66528kb

input:

1
120000
1 2
1 3
3 4
4 5
5 6
5 7
7 8
8 9
9 10
9 11
11 12
11 13
13 14
14 15
15 16
15 17
16 18
18 19
18 20
20 21
21 22
21 23
22 24
23 25
24 26
25 27
26 28
27 29
29 30
30 31
31 32
32 33
33 34
34 35
34 36
35 37
36 38
37 39
39 40
40 41
41 42
42 43
42 44
43 45
45 46
45 47
47 48
47 49
48 50
50 51
50 52
51 ...

output:

Yes

result:

ok single line: 'Yes'

Test #107:

score: 23
Accepted
time: 93ms
memory: 66584kb

input:

1
120000
1 2
2 3
2 4
4 5
5 6
6 7
7 8
7 9
8 10
10 11
10 12
12 13
12 14
13 15
14 16
16 17
17 18
17 19
18 20
20 21
20 22
22 23
22 24
23 25
24 26
25 27
26 28
27 29
29 30
29 31
30 32
32 33
33 34
34 35
35 36
35 37
37 38
38 39
39 40
40 41
41 42
42 43
42 44
43 45
45 46
45 47
47 48
47 49
49 50
50 51
50 52
51...

output:

No

result:

ok single line: 'No'

Extra Test:

score: 0
Extra Test Passed