QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#115110#3501. Jailst2023085161 281ms408848kbC++143.5kb2023-06-24 16:52:412023-06-24 16:52:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-24 16:52:44]
  • 评测
  • 测评结果:61
  • 用时:281ms
  • 内存:408848kb
  • [2023-06-24 16:52:41]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int N=5e6+9;
int Q,n,m,deg[N],dfn[N],tot,son[N],sz[N],top[N],fa[N],d[N],rt1,rt2,id1[N],id2[N],cnt,ls[N<<1],rs[N<<1],id=1;
vector<int> e[N],t[N];

void add(int x,int y) {deg[y]++, e[x].push_back(y);}
void prework(){
	memset(dfn,0,sizeof(dfn));
	memset(sz,0,sizeof(sz));
	memset(top,0,sizeof(top));
	memset(fa,0,sizeof(fa));
	memset(d,0,sizeof(d));
	memset(son,0,sizeof(son));
	memset(deg,0,sizeof(deg));
	for(int i=1;i<=n;i++){
	  	t[i].clear();
  	}
  	for(int i=1;i<=cnt;i++){
		e[i].clear(); 
  	}
	tot=cnt=0;
	for(int i=1;i<=id;i++){
		ls[i]=rs[i]=0;
	} 
	rt1=rt2=0;
	for(int i=1;i<=n;i++){
		id1[i]=id2[i]=0;
	} 
	id=1;
}

  
  void builds(int &p,int l,int r) {
    p=++id;
    if(l==r) {id1[l]=p; return;} int mid=l+r>>1;
    builds(ls[p],l,mid), builds(rs[p],mid+1,r);
    add(ls[p],p), add(rs[p],p);
  }
  void buildt(int &p,int l,int r) {
    p=++id;
    if(l==r) {id2[l]=p; return;} int mid=l+r>>1;
    buildt(ls[p],l,mid), buildt(rs[p],mid+1,r);
    add(p,ls[p]), add(p,rs[p]);
  }
  void adds(int p,int l,int r,int x,int y,int z) {
    assert(x);
    if(x>y) return;
    if(l==x&&r==y) {add(p,z); return;} int mid=l+r>>1;
    if(y<=mid) adds(ls[p],l,mid,x,y,z);
    else if(x>mid) adds(rs[p],mid+1,r,x,y,z);
    else adds(ls[p],l,mid,x,mid,z) ,adds(rs[p],mid+1,r,mid+1,y,z);
  }
  void addt(int p,int l,int r,int x,int y,int z) {
    if(x>y) return;
    if(l==x&&r==y) {add(z,p); return;} int mid=l+r>>1;
    if(y<=mid) addt(ls[p],l,mid,x,y,z);
    else if(x>mid) addt(rs[p],mid+1,r,x,y,z);
    else addt(ls[p],l,mid,x,mid,z), addt(rs[p],mid+1,r,mid+1,y,z);
  }


void dfs1(int u) {
  d[u]=d[fa[u]]+1, sz[u]=1;
  for(int v:t[u]) if(v!=fa[u]) {
    fa[v]=u, dfs1(v), sz[u]+=sz[v];
    if(sz[v]>sz[son[u]]) son[u]=v;
  }
}
void dfs2(int u,int tp) {
  dfn[u]=++tot;
  top[u]=tp; if(son[u]) dfs2(son[u],tp);
  for(int v:t[u]) if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
void work(int u,int v,int c) {
  if(d[u]<d[v]) swap(u,v);
  if(dfn[v]<=dfn[u]&&dfn[u]<dfn[v]+sz[v]) {
    u=fa[u];
    for(;top[u]!=top[v];u=fa[top[u]]) {
      adds(rt1,1,n,dfn[top[u]],dfn[u],c);
      addt(rt2,1,n,dfn[top[u]],dfn[u],c);
    }
    adds(rt1,1,n,dfn[v]+1,dfn[u],c);
    addt(rt2,1,n,dfn[v]+1,dfn[u],c);
  } else {
    u=fa[u], v=fa[v];
    for(;top[u]!=top[v];u=fa[top[u]]) {
      if(d[top[u]]<d[top[v]]) swap(u,v);
      adds(rt1,1,n,dfn[top[u]],dfn[u],c);
      addt(rt2,1,n,dfn[top[u]],dfn[u],c);
    }
    if(dfn[u]<dfn[v]) swap(u,v);
    adds(rt1,1,n,dfn[v],dfn[u],c);
    addt(rt2,1,n,dfn[v],dfn[u],c);
  }
}
bool topo(){//拓扑排序 
  	queue<int>q; 
  	for(int i=1;i<=cnt;i++){
  		if(!deg[i]) q.push(i);
  	}
  	while(!q.empty()){
    	int x=q.front();q.pop();
    	for(int y:e[x]){
			if(!(--deg[y])) q.push(y);
		} 
  	}
  	for(int i=1;i<=cnt;i++){
  		if(deg[i]) return 0;
  	}
  	return 1;
}

signed main() {
	ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin>>Q; 
  while(Q--) {
    cin>>n; 
    prework();
    rep(i,2,n) {
      int u, v;
      cin>>u>>v;
      t[u].push_back(v), t[v].push_back(u);
    }
    dfs1(1), dfs2(1,1);
    builds(rt1,1,n);
    buildt(rt2,1,n);
    cnt=id;
    cin>>m;
    rep(i,1,m) {
      int s, t; ++cnt;
      cin>>s>>t;
      add(id2[dfn[t]],cnt);
      add(cnt,id1[dfn[s]]);
      add(cnt,id2[dfn[s]]);
      add(id1[dfn[t]],cnt);
      work(s,t,cnt);
    }
    puts(topo()?"Yes":"No");
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 5
Accepted
time: 35ms
memory: 381132kb

input:

1
2
1 2
2
1 2
2 1

output:

No

result:

ok single line: 'No'

Test #2:

score: -5
Time Limit Exceeded

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:


result:


Subtask #2:

score: 5
Accepted

Test #21:

score: 5
Accepted
time: 242ms
memory: 381236kb

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: 0
Accepted
time: 225ms
memory: 381172kb

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: 0
Accepted
time: 215ms
memory: 381224kb

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: 0
Accepted
time: 229ms
memory: 381176kb

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: 0
Accepted
time: 232ms
memory: 381256kb

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: 0
Accepted
time: 244ms
memory: 381228kb

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: 0
Accepted
time: 230ms
memory: 381232kb

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: 0
Accepted
time: 198ms
memory: 381236kb

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: 0
Accepted
time: 234ms
memory: 381160kb

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: 0
Accepted
time: 225ms
memory: 379180kb

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

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: 0
Accepted
time: 240ms
memory: 381264kb

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: 0
Accepted
time: 214ms
memory: 381188kb

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: 0
Accepted
time: 242ms
memory: 381168kb

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: 0
Accepted
time: 224ms
memory: 379200kb

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: 0
Accepted
time: 219ms
memory: 381260kb

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: 0
Accepted
time: 229ms
memory: 381200kb

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: 0
Accepted
time: 230ms
memory: 381208kb

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: 0
Accepted
time: 232ms
memory: 381164kb

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: 0
Accepted
time: 244ms
memory: 381196kb

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: 0
Accepted
time: 238ms
memory: 381196kb

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: 0
Accepted
time: 234ms
memory: 381120kb

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

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: 0
Accepted
time: 223ms
memory: 381208kb

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: 0
Accepted
time: 210ms
memory: 381216kb

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: 0
Accepted
time: 221ms
memory: 381188kb

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: 0
Accepted
time: 227ms
memory: 381212kb

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: 0
Accepted
time: 237ms
memory: 381180kb

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: 0
Accepted
time: 239ms
memory: 379176kb

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: 0
Accepted
time: 225ms
memory: 381256kb

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

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: 0
Accepted
time: 281ms
memory: 382512kb

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: 0
Accepted
time: 262ms
memory: 382840kb

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: 0
Accepted
time: 235ms
memory: 380252kb

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: 0
Accepted
time: 227ms
memory: 381548kb

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: 0
Accepted
time: 89ms
memory: 399380kb

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: 0
Accepted
time: 93ms
memory: 401020kb

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: 0
Accepted
time: 83ms
memory: 408388kb

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: 0
Accepted
time: 81ms
memory: 408848kb

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: 0
Accepted
time: 64ms
memory: 403768kb

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: 0
Accepted
time: 76ms
memory: 399680kb

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: 0
Accepted
time: 71ms
memory: 405848kb

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: 0
Accepted
time: 68ms
memory: 405852kb

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: 0
Accepted
time: 240ms
memory: 382312kb

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: 0
Accepted
time: 75ms
memory: 401304kb

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: 0
Time Limit Exceeded

Test #66:

score: 0
Time Limit Exceeded

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:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

0%