QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#323394	#5670. Group Guests	ushg8877	AC ✓	778ms	572644kb	C++14	2.5kb	2024-02-09 15:11:08	2024-02-09 15:11:08

Judging History

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

[2024-02-09 15:11:08]
评测

测评结果：AC
用时：778ms
内存：572644kb

查看

[2024-02-09 15:11:08]
提交

answer

#include<bits/stdc++.h>
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=4e6+5,M=N*20+5,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(263082);
int m,n,X[N],Y[N],In[N];vector<int> S[N],G[N],P[N];
int flag,dfn[N],low[N],dh,st[N],sh,Ct,fa[N],Si[N];
int g[N],gs[N],sum;
vector<int> pot;
void dfs1(int x,int La){
	for(int i:P[x]) if(i^La) dfs1(i,x);
	int Ct=max(g[x]-1,0);
	for(int i:P[x]) if(i^La) Ct+=g[i]-1;
	if((g[x]+Si[x])&1) Ct++;
	for(int i:P[x]) if(i^La&&(Si[i]-g[i])%2==0) Ct++;
	if(x<=n&&Ct>=3) flag=1;
}
void con(int x,int y){P[x].emplace_back(y);P[y].emplace_back(x);}
void dfs2(int x,int La){
	pot.emplace_back(x);dfn[x]=low[x]=++dh;st[++sh]=x;sum+=S[x].size();
	for(int i:S[x]) if(i^La){
		if(dfn[i]) {low[x]=min(low[x],dfn[i]);continue;}dfs2(i,x);low[x]=min(low[x],low[i]);
		if(low[i]>=dfn[x]){con(++Ct,x);while(st[sh+1]^i) con(Ct,st[sh--]);}
	}
}
void dfs3(int x,int La){fa[x]=La;for(int i:P[x]) if(i^La) dfs3(i,x);}
void dfs4(int x,int La){for(int i:P[x]) if(i^La) dfs4(i,x),Si[x]+=Si[i];}
int check(int x,int y,int z){
	int cir=fa[x];if(fa[y]==fa[z]) cir=fa[y];
	auto find=[&cir](int x){
		if(fa[x]==cir){
			if(g[x]==2&&Si[x]&1) return 0;
		} else{
			if(g[cir]==2&&!(Si[cir]&1)) return 0;
		}
		return 1;
	};
	return find(x)&&find(y)&&find(z);
}
int calc(){
	for(int i:pot){
		for(int j:G[i]) gs[j]++;
		for(int j:G[i]) for(int h:G[j]) if(gs[h]&&check(i,j,h)) return 1;
		for(int j:G[i]) gs[j]=0;
	}
	return 0;
}
void Solve(){
	int i,j;scanf("%d%d",&m,&n);
	for(i=1;i<=m;i++) scanf("%d%d",&X[i],&Y[i]),In[X[i]]++,In[Y[i]]++;
	for(i=1;i<=m;i++) S[X[i]].emplace_back(Y[i]),S[Y[i]].emplace_back(X[i]);
	for(i=1;i<=m;i++){
		if(In[X[i]]>In[Y[i]]) swap(X[i],Y[i]);
		G[X[i]].emplace_back(Y[i]);
	} 
	int ans1=0,ans2=0;Ct=n;
	for(i=1;i<=n;i++) if(!dfn[i]){
		pot.clear();int LC=Ct;sh=sum=0;dfs2(i,0);if(!(sum>>1&1)) continue;dfs3(i,0);
		for(int j:pot) for(int h:S[j]) {
			if(fa[h]==fa[j]||fa[fa[j]]==h) g[j]++,dfn[j]<dfn[h]&&(Si[fa[j]]++);else g[fa[h]]++,dfn[j]<dfn[h]&&(Si[fa[h]]++);
		}
		dfs4(i,0);//if(i%1000==0) cerr<<pot.size()<<' '<<Ct<<' '<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
		if(calc()) continue;
		flag=0;dfs1(i,0);
		if(!flag) ans1++;
		else ans2++;
	}
	printf("%d %d\n",ans1,ans2);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 39ms

memory: 285316kb

input:

2 4
1 2
3 4

output:

2 0

result:

ok single line: '2 0'

Test #2:

score: 0

Accepted

time: 47ms

memory: 285272kb

input:

2 3
1 2
3 1

output:

0 0

result:

ok single line: '0 0'

Test #3:

score: 0

Accepted

time: 35ms

memory: 285220kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #4:

score: 0

Accepted

time: 284ms

memory: 379632kb

input:

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

output:

383 523

result:

ok single line: '383 523'

Test #5:

score: 0

Accepted

time: 271ms

memory: 379608kb

input:

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

output:

349 522

result:

ok single line: '349 522'

Test #6:

score: 0

Accepted

time: 32ms

memory: 285264kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #7:

score: 0

Accepted

time: 312ms

memory: 377292kb

input:

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

output:

375 322

result:

ok single line: '375 322'

Test #8:

score: 0

Accepted

time: 303ms

memory: 377348kb

input:

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

output:

366 307

result:

ok single line: '366 307'

Test #9:

score: 0

Accepted

time: 40ms

memory: 285280kb

input:

output:

0 1

result:

ok single line: '0 1'

Test #10:

score: 0

Accepted

time: 325ms

memory: 384720kb

input:

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

output:

1032 1376

result:

ok single line: '1032 1376'

Test #11:

score: 0

Accepted

time: 299ms

memory: 384764kb

input:

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

output:

990 1439

result:

ok single line: '990 1439'

Test #12:

score: 0

Accepted

time: 39ms

memory: 285280kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #13:

score: 0

Accepted

time: 27ms

memory: 285280kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #14:

score: 0

Accepted

time: 56ms

memory: 285260kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #15:

score: 0

Accepted

time: 36ms

memory: 285272kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #16:

score: 0

Accepted

time: 31ms

memory: 285284kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #17:

score: 0

Accepted

time: 35ms

memory: 285280kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #18:

score: 0

Accepted

time: 27ms

memory: 285332kb

input:

output:

0 1

result:

ok single line: '0 1'

Test #19:

score: 0

Accepted

time: 39ms

memory: 285292kb

input:

output:

0 1

result:

ok single line: '0 1'

Test #20:

score: 0

Accepted

time: 35ms

memory: 285232kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #21:

score: 0

Accepted

time: 31ms

memory: 285332kb

input:

output:

1 0

result:

ok single line: '1 0'

Test #22:

score: 0

Accepted

time: 44ms

memory: 285312kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #23:

score: 0

Accepted

time: 32ms

memory: 285340kb

input:

output:

18 4

result:

ok single line: '18 4'

Test #24:

score: 0

Accepted

time: 53ms

memory: 285248kb

input:

output:

1 0

result:

ok single line: '1 0'

Test #25:

score: 0

Accepted

time: 47ms

memory: 286000kb

input:

output:

142 140

result:

ok single line: '142 140'

Test #26:

score: 0

Accepted

time: 36ms

memory: 285252kb

input:

output:

0 1

result:

ok single line: '0 1'

Test #27:

score: 0

Accepted

time: 87ms

memory: 312544kb

input:

245745 196512
1 2
1 3
7 8
7 10
13 15
13 16
19 20
19 21
19 22
25 26
25 29
31 33
31 35
37 38
37 39
37 41
43 46
43 47
49 50
49 52
49 53
55 57
55 58
55 59
61 62
61 63
61 64
61 65
67 68
67 72
73 75
73 78
79 80
79 81
79 84
85 88
85 90
91 92
91 94
91 96
97 99
97 100
97 102
103 104
103 105
103 106
103 108
1...

output:

2097 2626

result:

ok single line: '2097 2626'

Test #28:

score: 0

Accepted

time: 39ms

memory: 285252kb

input:

output:

0 1

result:

ok single line: '0 1'

Test #29:

score: 0

Accepted

time: 313ms

memory: 402024kb

input:

999999 841330
1 2
1 3
8 9
8 11
15 17
15 18
22 23
22 24
22 25
29 30
29 33
36 38
36 40
43 44
43 45
43 47
50 53
50 54
57 58
57 60
57 61
64 66
64 67
64 68
71 72
71 73
71 74
71 75
78 79
78 83
85 87
85 90
92 93
92 94
92 97
99 102
99 104
106 107
106 109
106 111
113 115
113 116
113 118
120 121
120 122
120 1...

output:

7646 12754

result:

ok single line: '7646 12754'

Test #30:

score: 0

Accepted

time: 285ms

memory: 390896kb

input:

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

output:

3532 7627

result:

ok single line: '3532 7627'

Test #31:

score: 0

Accepted

time: 284ms

memory: 389160kb

input:

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

output:

3201 7345

result:

ok single line: '3201 7345'

Test #32:

score: 0

Accepted

time: 276ms

memory: 384716kb

input:

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

output:

2402 4121

result:

ok single line: '2402 4121'

Test #33:

score: 0

Accepted

time: 262ms

memory: 376120kb

input:

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

output:

943 2394

result:

ok single line: '943 2394'

Test #34:

score: 0

Accepted

time: 263ms

memory: 390800kb

input:

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

output:

3698 7209

result:

ok single line: '3698 7209'

Test #35:

score: 0

Accepted

time: 272ms

memory: 381564kb

input:

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

output:

1310 3756

result:

ok single line: '1310 3756'

Test #36:

score: 0

Accepted

time: 259ms

memory: 379216kb

input:

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

output:

835 3556

result:

ok single line: '835 3556'

Test #37:

score: 0

Accepted

time: 280ms

memory: 375896kb

input:

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

output:

331 2414

result:

ok single line: '331 2414'

Test #38:

score: 0

Accepted

time: 264ms

memory: 373692kb

input:

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

output:

164 2050

result:

ok single line: '164 2050'

Test #39:

score: 0

Accepted

time: 255ms

memory: 381440kb

input:

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

output:

3578 4667

result:

ok single line: '3578 4667'

Test #40:

score: 0

Accepted

time: 283ms

memory: 384708kb

input:

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

output:

1590 5625

result:

ok single line: '1590 5625'

Test #41:

score: 0

Accepted

time: 243ms

memory: 377420kb

input:

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

output:

653 1686

result:

ok single line: '653 1686'

Test #42:

score: 0

Accepted

time: 277ms

memory: 381520kb

input:

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

output:

944 4865

result:

ok single line: '944 4865'

Test #43:

score: 0

Accepted

time: 276ms

memory: 374700kb

input:

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

output:

256 2136

result:

ok single line: '256 2136'

Test #44:

score: 0

Accepted

time: 245ms

memory: 368804kb

input:

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

output:

223 715

result:

ok single line: '223 715'

Test #45:

score: 0

Accepted

time: 258ms

memory: 381612kb

input:

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

output:

931 4522

result:

ok single line: '931 4522'

Test #46:

score: 0

Accepted

time: 263ms

memory: 374556kb

input:

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

output:

151 2420

result:

ok single line: '151 2420'

Test #47:

score: 0

Accepted

time: 235ms

memory: 370384kb

input:

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

output:

396 361

result:

ok single line: '396 361'

Test #48:

score: 0

Accepted

time: 255ms

memory: 372692kb

input:

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

output:

277 414

result:

ok single line: '277 414'

Test #49:

score: 0

Accepted

time: 233ms

memory: 368360kb

input:

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

output:

104 179

result:

ok single line: '104 179'

Test #50:

score: 0

Accepted

time: 248ms

memory: 363324kb

input:

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

output:

102 6

result:

ok single line: '102 6'

Test #51:

score: 0

Accepted

time: 46ms

memory: 286568kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #52:

score: 0

Accepted

time: 31ms

memory: 285300kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #53:

score: 0

Accepted

time: 250ms

memory: 372316kb

input:

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

output:

38 1247

result:

ok single line: '38 1247'

Test #54:

score: 0

Accepted

time: 214ms

memory: 359948kb

input:

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

output:

8 0

result:

ok single line: '8 0'

Test #55:

score: 0

Accepted

time: 228ms

memory: 357120kb

input:

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

output:

7 0

result:

ok single line: '7 0'

Test #56:

score: 0

Accepted

time: 257ms

memory: 370776kb

input:

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

output:

10 374

result:

ok single line: '10 374'

Test #57:

score: 0

Accepted

time: 259ms

memory: 372300kb

input:

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

output:

656 1809

result:

ok single line: '656 1809'

Test #58:

score: 0

Accepted

time: 36ms

memory: 285336kb

input:

output:

1 0

result:

ok single line: '1 0'

Test #59:

score: 0

Accepted

time: 265ms

memory: 367340kb

input:

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

output:

123 0

result:

ok single line: '123 0'

Test #60:

score: 0

Accepted

time: 280ms

memory: 370960kb

input:

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

output:

57 40

result:

ok single line: '57 40'

Test #61:

score: 0

Accepted

time: 43ms

memory: 285280kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #62:

score: 0

Accepted

time: 778ms

memory: 448784kb

input:

999999 1000000
1 560136
2 102142
2 236736
3 309371
3 491463
4 538764
5 470246
6 278170
7 227277
8 673767
9 37182
9 231457
11 414293
11 583390
11 812999
11 868721
11 925233
12 254802
12 517049
12 530488
12 910757
12 943612
13 901211
14 1496
14 802703
15 684146
18 159626
18 209532
18 394262
18 583396
...

output:

20012 719

result:

ok single line: '20012 719'

Test #63:

score: 0

Accepted

time: 117ms

memory: 310576kb

input:

998991 1414
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...

output:

0 0

result:

ok single line: '0 0'

Test #64:

score: 0

Accepted

time: 311ms

memory: 546268kb

input:

999999 999999
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 ...

output:

1 0

result:

ok single line: '1 0'

Test #65:

score: 0

Accepted

time: 321ms

memory: 488632kb

input:

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

output:

0 1

result:

ok single line: '0 1'

Test #66:

score: 0

Accepted

time: 320ms

memory: 472948kb

input:

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

output:

0 0

result:

ok single line: '0 0'

Test #67:

score: 0

Accepted

time: 440ms

memory: 572644kb

input:

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

output:

1 0

result:

ok single line: '1 0'

Test #68:

score: 0

Accepted

time: 350ms

memory: 411488kb

input:

999915 952300
1 41
1 47
1 72
2 16
2 88
2 95
3 9
3 26
3 91
4 21
4 37
4 85
5 14
5 49
5 88
6 25
7 71
7 74
7 84
8 22
9 34
9 83
10 16
10 90
11 18
12 35
12 52
14 17
14 44
14 72
15 26
15 80
15 83
16 42
17 65
18 29
18 85
19 41
19 74
21 38
22 25
22 37
22 53
23 38
24 39
24 63
24 98
25 64
25 91
26 44
26 55
26 ...

output:

15511 1803

result:

ok single line: '15511 1803'

Test #69:

score: 0

Accepted

time: 359ms

memory: 415300kb

input:

999975 995000
1 359
1 729
1 966
2 263
2 487
4 372
4 391
4 877
5 883
6 248
6 254
6 703
7 141
7 333
8 496
8 602
8 934
9 747
10 283
11 386
11 815
12 954
13 963
14 437
14 891
15 274
15 826
16 56
16 278
16 893
18 247
18 789
18 826
19 409
19 695
20 158
20 624
20 838
20 993
21 289
21 734
22 936
22 938
23 2...

output:

19402 813

result:

ok single line: '19402 813'

Test #70:

score: 0

Accepted

time: 391ms

memory: 413656kb

input:

990495 990000
1 4654
2 553
2 4245
3 2524
3 3264
3 4715
3 5674
3 8204
4 5011
5 2857
5 9071
6 1514
6 5066
6 6536
6 7994
7 827
7 6412
8 7290
9 871
9 1936
9 2124
9 6867
11 8860
12 1347
12 3879
12 8952
13 1635
13 3529
14 3313
14 7551
14 8286
15 307
15 614
15 6202
15 7888
15 7935
16 2070
17 689
18 2352
18...

output:

19786 687

result:

ok single line: '19786 687'

Test #71:

score: 0

Accepted

time: 333ms

memory: 407276kb

input:

999955 909050
1 4
1 13
1 28
1 33
1 36
2 25
3 42
4 16
5 25
7 22
7 24
7 30
7 33
7 40
7 50
8 19
8 27
9 17
9 24
10 19
10 20
10 24
10 37
12 34
13 32
13 36
14 36
15 24
16 20
16 31
17 22
18 24
19 32
19 37
19 43
20 27
20 44
21 27
21 33
24 31
24 36
24 41
25 26
26 44
27 28
27 39
27 40
28 36
28 49
30 37
30 39
...

output:

11763 2903

result:

ok single line: '11763 2903'

Test #72:

score: 0

Accepted

time: 381ms

memory: 415040kb

input:

999900 990000
1 33
1 290
1 323
1 327
1 341
2 12
2 17
2 46
2 198
3 204
3 256
4 27
4 313
6 236
7 217
9 153
9 431
10 21
10 415
10 419
11 58
12 55
12 128
14 390
15 34
16 240
16 321
17 262
18 231
18 238
19 78
19 130
19 266
19 271
20 203
20 474
20 494
21 25
21 429
22 348
22 484
23 388
23 463
24 209
24 243...

output:

19065 967

result:

ok single line: '19065 967'

Test #73:

score: 0

Accepted

time: 407ms

memory: 415144kb

input:

995995 995000
1 516
1 2254
1 3620
2 3500
3 184
3 917
3 1224
3 3467
3 4653
4 537
5 3604
6 687
6 1559
6 4129
7 462
7 1012
7 2094
7 2665
7 4363
7 4473
8 300
8 307
8 1678
8 2921
8 4070
9 3102
9 4561
11 1749
11 3944
11 4927
12 1479
12 3635
13 492
14 1693
14 2362
14 4867
15 2073
15 2166
15 2186
16 1523
16...

output:

19765 706

result:

ok single line: '19765 706'

Test #74:

score: 0

Accepted

time: 199ms

memory: 356256kb

input:

999905 196061
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
3 11
3 12
3 13
3 14
3 15
3 16
3 17
3 18
3 19
3 20
4 11
4 12
4 13
4 14
4 15
4 16
4 17
4 18
4 19
4 20
5 11
5 12
5 13
5 14
5 15
5 16
5 17
5 18
5 19
5 20
6 11
6 12
6 13
6 14
6 15
6 16
6 17
6...

output:

0 1

result:

ok single line: '0 1'

Test #75:

score: 0

Accepted

time: 191ms

memory: 356160kb

input:

999905 196061
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
3 11
3 12
3 13
3 14
3 15
3 16
3 17
3 18
3 19
3 20
4 11
4 12
4 13
4 14
4 15
4 16
4 17
4 18
4 19
4 20
5 11
5 12
5 13
5 14
5 15
5 16
5 17
5 18
5 19
5 20
6 11
6 12
6 13
6 14
6 15
6 16
6 17
6...

output:

0 0

result:

ok single line: '0 0'

Test #76:

score: 0

Accepted

time: 314ms

memory: 414860kb

input:

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

output:

1 0

result:

ok single line: '1 0'