QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#185927	#5670. Group Guests	275307894a	AC ✓	835ms	589328kb	C++14	2.9kb	2023-09-22 20:29:19	2023-09-22 20:29:20

Judging History

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

[2023-09-22 20:29:20]
评测

测评结果：AC
用时：835ms
内存：589328kb

查看

[2023-09-22 20:29:19]
提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
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);/*cerr<<"Pt "<<Ct<<'\n'<<x<<' ';*/while(st[sh+1]^i) /*cerr<<st[sh]<<' ',*/con(Ct,st[sh--]);/*cerr<<'\n';*/}
	}
}
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){
	cerr<<x<<' '<<y<<' '<<z<<'\n';
	int cir=fa[x];if(fa[y]==fa[z]) cir=fa[y];
	cerr<<cir<<'\n';
	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;
	};
	cerr<<find(z)<<'\n';
	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: 36ms

memory: 300964kb

input:

2 4
1 2
3 4

output:

2 0

result:

ok single line: '2 0'

Test #2:

score: 0

Accepted

time: 43ms

memory: 292796kb

input:

2 3
1 2
3 1

output:

0 0

result:

ok single line: '0 0'

Test #3:

score: 0

Accepted

time: 48ms

memory: 298796kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #4:

score: 0

Accepted

time: 420ms

memory: 393184kb

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: 413ms

memory: 395272kb

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

input:

output:

0 0

result:

ok single line: '0 0'

Test #7:

score: 0

Accepted

time: 398ms

memory: 391548kb

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: 413ms

memory: 391428kb

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: 32ms

memory: 298936kb

input:

output:

0 1

result:

ok single line: '0 1'

Test #10:

score: 0

Accepted

time: 444ms

memory: 400852kb

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: 420ms

memory: 398096kb

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: 31ms

memory: 294840kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #13:

score: 0

Accepted

time: 40ms

memory: 298920kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #14:

score: 0

Accepted

time: 43ms

memory: 292736kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #15:

score: 0

Accepted

time: 40ms

memory: 294848kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #16:

score: 0

Accepted

time: 47ms

memory: 298928kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #17:

score: 0

Accepted

time: 32ms

memory: 292780kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #18:

score: 0

Accepted

time: 48ms

memory: 300980kb

input:

output:

0 1

result:

ok single line: '0 1'

Test #19:

score: 0

Accepted

time: 40ms

memory: 298948kb

input:

output:

0 1

result:

ok single line: '0 1'

Test #20:

score: 0

Accepted

time: 24ms

memory: 292732kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #21:

score: 0

Accepted

time: 31ms

memory: 298972kb

input:

output:

1 0

result:

ok single line: '1 0'

Test #22:

score: 0

Accepted

time: 27ms

memory: 298892kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #23:

score: 0

Accepted

time: 30ms

memory: 301024kb

input:

output:

18 4

result:

ok single line: '18 4'

Test #24:

score: 0

Accepted

time: 40ms

memory: 298924kb

input:

output:

1 0

result:

ok single line: '1 0'

Test #25:

score: 0

Accepted

time: 36ms

memory: 301512kb

input:

output:

142 140

result:

ok single line: '142 140'

Test #26:

score: 0

Accepted

time: 31ms

memory: 298936kb

input:

output:

0 1

result:

ok single line: '0 1'

Test #27:

score: 0

Accepted

time: 119ms

memory: 326596kb

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: 41ms

memory: 298936kb

input:

output:

0 1

result:

ok single line: '0 1'

Test #29:

score: 0

Accepted

time: 434ms

memory: 415456kb

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: 359ms

memory: 405448kb

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: 362ms

memory: 403916kb

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: 399ms

memory: 399320kb

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: 320ms

memory: 390840kb

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: 335ms

memory: 405680kb

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: 364ms

memory: 397640kb

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: 364ms

memory: 396420kb

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: 376ms

memory: 387084kb

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: 351ms

memory: 387816kb

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: 358ms

memory: 397052kb

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: 385ms

memory: 400864kb

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: 390ms

memory: 390212kb

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: 322ms

memory: 396668kb

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: 332ms

memory: 390824kb

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: 368ms

memory: 381528kb

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: 347ms

memory: 392960kb

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: 301ms

memory: 391192kb

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: 331ms

memory: 385836kb

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: 332ms

memory: 387044kb

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: 346ms

memory: 384468kb

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: 337ms

memory: 377732kb

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: 47ms

memory: 302020kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #52:

score: 0

Accepted

time: 31ms

memory: 294852kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #53:

score: 0

Accepted

time: 316ms

memory: 387732kb

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: 302ms

memory: 372300kb

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: 300ms

memory: 371608kb

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: 303ms

memory: 387888kb

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: 330ms

memory: 387228kb

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: 39ms

memory: 298912kb

input:

output:

1 0

result:

ok single line: '1 0'

Test #59:

score: 0

Accepted

time: 254ms

memory: 390316kb

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: 411ms

memory: 388032kb

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: 30ms

memory: 294828kb

input:

output:

0 0

result:

ok single line: '0 0'

Test #62:

score: 0

Accepted

time: 652ms

memory: 469352kb

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: 134ms

memory: 324540kb

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: 273ms

memory: 561056kb

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: 835ms

memory: 504436kb

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: 724ms

memory: 489048kb

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: 427ms

memory: 589328kb

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: 365ms

memory: 426496kb

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: 350ms

memory: 432128kb

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: 442ms

memory: 431548kb

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: 375ms

memory: 422424kb

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: 376ms

memory: 429948kb

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: 401ms

memory: 428016kb

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: 220ms

memory: 370508kb

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: 220ms

memory: 371284kb

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: 298ms

memory: 431128kb

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'