QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#291265#2660. Agencizhouhuanyi100 ✓201ms79044kbC++201.4kb2023-12-26 09:38:282023-12-26 09:38:28

Judging History

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

  • [2023-12-26 09:38:28]
  • 评测
  • 测评结果：100
  • 用时：201ms
  • 内存：79044kb
查看
  • [2023-12-26 09:38:28]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#define N 500000
using namespace std;
const int inf=(int)(1e9);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int n,k,dp[N+1][2][2],F[2][2];
bool cl[N+1],used[N+1];
vector<int>E[N+1];
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
void dfs(int x)
{
	used[x]=1,dp[x][cl[x]][0]=dp[x][cl[x]][1]=0;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
		{
			dfs(E[x][i]);
			for (int op=0;op<=1;++op)
				for (int op2=0;op2<=1;++op2)
					F[op][op2]=inf;
			for (int op=0;op<=1;++op)
				for (int op2=0;op2<=1;++op2)
					F[op][op2]=min(F[op][op2],dp[x][op][op2]+dp[E[x][i]][1][1]);
			for (int op=0;op<=1;++op)
				for (int op2=0;op2<=1;++op2)
					for (int opt=0;op+opt<=1;++opt)
						for (int opt2=0;op2+opt2<=1;++opt2)
							F[op+opt][op2+opt2]=min(F[op+opt][op2+opt2],dp[x][op][op2]+dp[E[x][i]][opt][opt2]+2-(opt^opt2));
			for (int op=0;op<=1;++op)
				for (int op2=0;op2<=1;++op2)
					dp[x][op][op2]=F[op][op2];
		}
	return;
}
int main()
{
	int x,y;
	n=read(),k=read();
	for (int i=1;i<=k;++i) x=read(),cl[x]=1;
	for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
	for (int i=1;i<=n;++i)
		for (int op=0;op<=1;++op)
			for (int op2=0;op2<=1;++op2)
				dp[i][op][op2]=inf;
	dfs(1),printf("%d\n",dp[1][1][1]);
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 0ms
memory: 17460kb

input:

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

output:

12

result:

ok single line: '12'

Test #2:

score: 0
Accepted
time: 0ms
memory: 16996kb

input:

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

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 0ms
memory: 17512kb

input:

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

output:

8

result:

ok single line: '8'

Test #4:

score: 0
Accepted
time: 0ms
memory: 17424kb

input:

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

output:

9

result:

ok single line: '9'

Test #5:

score: 0
Accepted
time: 3ms
memory: 17888kb

input:

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

output:

8

result:

ok single line: '8'

Test #6:

score: 0
Accepted
time: 2ms
memory: 18048kb

input:

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

output:

14

result:

ok single line: '14'

Test #7:

score: 0
Accepted
time: 0ms
memory: 18300kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 0ms
memory: 20192kb

input:

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

output:

13

result:

ok single line: '13'

Test #9:

score: 0
Accepted
time: 0ms
memory: 17604kb

input:

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

output:

5

result:

ok single line: '5'

Test #10:

score: 0
Accepted
time: 0ms
memory: 18236kb

input:

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

output:

15

result:

ok single line: '15'

Test #11:

score: 0
Accepted
time: 4ms
memory: 17208kb

input:

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

output:

16

result:

ok single line: '16'

Test #12:

score: 0
Accepted
time: 3ms
memory: 17016kb

input:

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

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 0ms
memory: 17484kb

input:

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

output:

17

result:

ok single line: '17'

Test #14:

score: 0
Accepted
time: 0ms
memory: 17032kb

input:

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

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 3ms
memory: 17660kb

input:

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

output:

1

result:

ok single line: '1'

Test #16:

score: 0
Accepted
time: 0ms
memory: 17116kb

input:

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

output:

12

result:

ok single line: '12'

Test #17:

score: 0
Accepted
time: 4ms
memory: 18292kb

input:

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

output:

7

result:

ok single line: '7'

Test #18:

score: 0
Accepted
time: 0ms
memory: 18492kb

input:

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

output:

9

result:

ok single line: '9'

Test #19:

score: 0
Accepted
time: 3ms
memory: 16936kb

input:

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

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 0ms
memory: 16656kb

input:

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

output:

14

result:

ok single line: '14'

Test #21:

score: 0
Accepted
time: 0ms
memory: 17908kb

input:

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

output:

5

result:

ok single line: '5'

Test #22:

score: 0
Accepted
time: 3ms
memory: 16900kb

input:

9 1
8
7 8
7 1
6 3
2 3
7 3
5 9
4 9
3 9

output:

12

result:

ok single line: '12'

Test #23:

score: 0
Accepted
time: 4ms
memory: 18216kb

input:

9 8
1 2 3 4 5 6 8 9
4 2
4 3
5 1
8 1
4 1
7 9
6 9
1 9

output:

1

result:

ok single line: '1'

Test #24:

score: 0
Accepted
time: 4ms
memory: 18452kb

input:

9 1
9
3 4
3 7
1 9
5 1
1 3
8 2
6 8
1 8

output:

13

result:

ok single line: '13'

Test #25:

score: 0
Accepted
time: 0ms
memory: 17288kb

input:

9 6
1 2 3 4 6 9
4 7
7 9
8 6
8 1
7 8
3 5
2 5
8 5

output:

3

result:

ok single line: '3'

Test #26:

score: 0
Accepted
time: 0ms
memory: 20232kb

input:

9 1
8
7 8
4 8
6 9
2 6
6 8
3 5
3 1
3 6

output:

13

result:

ok single line: '13'

Test #27:

score: 0
Accepted
time: 0ms
memory: 17452kb

input:

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

output:

15

result:

ok single line: '15'

Test #28:

score: 0
Accepted
time: 0ms
memory: 18048kb

input:

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

output:

1

result:

ok single line: '1'

Test #29:

score: 0
Accepted
time: 0ms
memory: 18356kb

input:

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

output:

16

result:

ok single line: '16'

Test #30:

score: 0
Accepted
time: 4ms
memory: 17992kb

input:

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

output:

4

result:

ok single line: '4'

Test #31:

score: 0
Accepted
time: 0ms
memory: 18020kb

input:

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

output:

16

result:

ok single line: '16'

Test #32:

score: 0
Accepted
time: 4ms
memory: 17000kb

input:

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

output:

10

result:

ok single line: '10'

Test #33:

score: 0
Accepted
time: 3ms
memory: 17072kb

input:

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

output:

9

result:

ok single line: '9'

Test #34:

score: 0
Accepted
time: 3ms
memory: 16924kb

input:

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

output:

9

result:

ok single line: '9'

Test #35:

score: 0
Accepted
time: 3ms
memory: 16624kb

input:

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

output:

15

result:

ok single line: '15'

Test #36:

score: 0
Accepted
time: 0ms
memory: 18008kb

input:

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

output:

0

result:

ok single line: '0'

Subtask #2:

score: 13
Accepted

Dependency #1:

100%
Accepted

Test #37:

score: 13
Accepted
time: 0ms
memory: 17444kb

input:

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

output:

18

result:

ok single line: '18'

Test #38:

score: 0
Accepted
time: 0ms
memory: 18016kb

input:

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

output:

2

result:

ok single line: '2'

Test #39:

score: 0
Accepted
time: 0ms
memory: 18152kb

input:

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

output:

18

result:

ok single line: '18'

Test #40:

score: 0
Accepted
time: 0ms
memory: 17208kb

input:

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

output:

19

result:

ok single line: '19'

Test #41:

score: 0
Accepted
time: 0ms
memory: 17108kb

input:

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

output:

18

result:

ok single line: '18'

Test #42:

score: 0
Accepted
time: 4ms
memory: 18040kb

input:

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

output:

28

result:

ok single line: '28'

Test #43:

score: 0
Accepted
time: 0ms
memory: 18012kb

input:

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

output:

1

result:

ok single line: '1'

Test #44:

score: 0
Accepted
time: 0ms
memory: 18152kb

input:

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

output:

31

result:

ok single line: '31'

Test #45:

score: 0
Accepted
time: 3ms
memory: 17016kb

input:

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

output:

10

result:

ok single line: '10'

Test #46:

score: 0
Accepted
time: 4ms
memory: 17892kb

input:

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

output:

34

result:

ok single line: '34'

Test #47:

score: 0
Accepted
time: 0ms
memory: 16944kb

input:

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

output:

30

result:

ok single line: '30'

Test #48:

score: 0
Accepted
time: 3ms
memory: 16784kb

input:

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

output:

1

result:

ok single line: '1'

Test #49:

score: 0
Accepted
time: 4ms
memory: 17792kb

input:

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

output:

37

result:

ok single line: '37'

Test #50:

score: 0
Accepted
time: 0ms
memory: 17608kb

input:

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

output:

31

result:

ok single line: '31'

Test #51:

score: 0
Accepted
time: 3ms
memory: 17104kb

input:

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

output:

1

result:

ok single line: '1'

Test #52:

score: 0
Accepted
time: 0ms
memory: 18248kb

input:

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

output:

25

result:

ok single line: '25'

Test #53:

score: 0
Accepted
time: 0ms
memory: 18152kb

input:

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

output:

14

result:

ok single line: '14'

Test #54:

score: 0
Accepted
time: 0ms
memory: 17128kb

input:

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

output:

27

result:

ok single line: '27'

Test #55:

score: 0
Accepted
time: 0ms
memory: 17236kb

input:

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

output:

0

result:

ok single line: '0'

Test #56:

score: 0
Accepted
time: 0ms
memory: 18304kb

input:

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

output:

33

result:

ok single line: '33'

Test #57:

score: 0
Accepted
time: 0ms
memory: 16700kb

input:

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

output:

12

result:

ok single line: '12'

Test #58:

score: 0
Accepted
time: 0ms
memory: 17716kb

input:

18 4
3 7 10 18
8 4
1 4
17 3
15 17
17 4
10 11
14 11
11 17
18 16
18 13
18 11
9 2
9 6
9 18
5 7
5 12
5 9

output:

19

result:

ok single line: '19'

Test #59:

score: 0
Accepted
time: 0ms
memory: 17776kb

input:

18 16
1 2 4 5 6 7 9 10 11 12 13 14 15 16 17 18
2 1
18 1
7 10
4 10
1 10
6 17
6 9
10 6
14 11
15 11
6 11
8 13
12 8
8 11
16 5
3 16
8 16

output:

2

result:

ok single line: '2'

Test #60:

score: 0
Accepted
time: 0ms
memory: 17116kb

input:

18 1
5
2 9
13 2
18 12
18 5
2 18
14 8
4 14
14 18
11 10
6 10
10 14
7 16
16 1
16 10
15 3
3 17
16 3

output:

28

result:

ok single line: '28'

Test #61:

score: 0
Accepted
time: 0ms
memory: 17092kb

input:

18 12
2 3 4 5 6 10 11 12 15 16 17 18
2 13
13 15
11 8
8 12
8 13
1 17
1 18
8 1
9 6
4 9
9 1
3 14
16 14
14 9
10 7
5 7
14 7

output:

6

result:

ok single line: '6'

Test #62:

score: 0
Accepted
time: 0ms
memory: 16588kb

input:

18 1
15
7 15
15 3
14 13
17 13
13 15
1 11
8 11
13 11
4 16
16 18
16 11
12 2
12 5
12 16
9 6
9 10
9 12

output:

28

result:

ok single line: '28'

Test #63:

score: 0
Accepted
time: 4ms
memory: 17736kb

input:

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

output:

31

result:

ok single line: '31'

Test #64:

score: 0
Accepted
time: 0ms
memory: 17852kb

input:

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

output:

1

result:

ok single line: '1'

Test #65:

score: 0
Accepted
time: 0ms
memory: 17004kb

input:

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

output:

27

result:

ok single line: '27'

Test #66:

score: 0
Accepted
time: 0ms
memory: 16544kb

input:

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

output:

5

result:

ok single line: '5'

Test #67:

score: 0
Accepted
time: 3ms
memory: 17684kb

input:

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

output:

36

result:

ok single line: '36'

Test #68:

score: 0
Accepted
time: 3ms
memory: 17732kb

input:

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

output:

23

result:

ok single line: '23'

Test #69:

score: 0
Accepted
time: 0ms
memory: 16912kb

input:

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

output:

18

result:

ok single line: '18'

Test #70:

score: 0
Accepted
time: 0ms
memory: 18208kb

input:

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

output:

19

result:

ok single line: '19'

Test #71:

score: 0
Accepted
time: 0ms
memory: 17612kb

input:

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

output:

32

result:

ok single line: '32'

Test #72:

score: 0
Accepted
time: 0ms
memory: 17296kb

input:

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

output:

0

result:

ok single line: '0'

Subtask #3:

score: 27
Accepted

Dependency #2:

100%
Accepted

Test #73:

score: 27
Accepted
time: 0ms
memory: 16904kb

input:

2000 15
87 235 346 501 506 789 858 1117 1279 1307 1398 1482 1625 1653 1671
231 873
809 873
362 809
826 362
451 826
451 338
1248 338
1117 1248
1117 1362
898 1362
898 1763
1991 1763
1991 732
732 1765
529 1765
581 529
581 328
570 328
570 1821
1821 454
1676 454
1676 94
1135 94
1135 996
996 440
440 401
4...

output:

1989

result:

ok single line: '1989'

Test #74:

score: 0
Accepted
time: 4ms
memory: 18552kb

input:

2000 1972
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

output:

28

result:

ok single line: '28'

Test #75:

score: 0
Accepted
time: 3ms
memory: 18608kb

input:

2000 2
686 1675
686 1190
23 1190
467 23
866 467
866 1877
1877 1679
780 1679
780 41
41 1248
1248 540
540 656
957 656
957 1458
270 1458
270 1610
1610 1443
457 1443
1626 457
1626 16
1013 16
1013 66
1301 66
1301 113
113 1756
1394 1756
1394 763
763 1173
1173 605
605 398
1043 398
1552 1043
1552 210
210 65...

output:

1998

result:

ok single line: '1998'

Test #76:

score: 0
Accepted
time: 0ms
memory: 17400kb

input:

2000 1
1187
1187 1424
490 1424
490 1791
751 1791
751 744
744 356
356 413
413 622
622 1218
1600 1218
486 1600
762 486
1770 762
1770 398
109 398
109 131
826 131
826 1936
1936 1828
1828 1643
1643 1820
1820 1579
1579 1607
1607 312
312 1803
1751 1803
1945 1751
750 1945
351 750
351 1189
1189 539
650 539
6...

output:

1999

result:

ok single line: '1999'

Test #77:

score: 0
Accepted
time: 4ms
memory: 16692kb

input:

2000 2
1263 1637
1263 1637
1637 894
868 894
147 868
10 147
10 1523
1523 765
765 1372
1372 1262
1262 109
357 109
1941 357
79 1941
1823 79
688 1823
688 254
254 1607
1607 1302
1697 1302
20 1697
1141 20
1141 1099
1099 1402
310 1402
310 1892
1892 511
511 144
1759 144
44 1759
333 44
1322 333
1355 1322
135...

output:

1998

result:

ok single line: '1998'

Test #78:

score: 0
Accepted
time: 0ms
memory: 18544kb

input:

2000 20
46 97 182 331 428 492 574 748 769 1028 1040 1069 1255 1284 1371 1380 1643 1689 1930 1945
1854 1852
1852 698
1854 1948
716 1854
698 890
698 115
1666 1948
1291 1948
716 705
716 1312
890 811
1236 890
115 977
115 850
14 1666
1666 1778
1291 1951
1056 1291
705 1945
705 1252
120 1312
1351 1312
811 ...

output:

3761

result:

ok single line: '3761'

Test #79:

score: 0
Accepted
time: 0ms
memory: 16620kb

input:

2000 1984
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

16

result:

ok single line: '16'

Test #80:

score: 0
Accepted
time: 0ms
memory: 18492kb

input:

2000 11
63 297 624 759 903 1021 1218 1655 1684 1762 1779
1634 1453
573 1453
1634 1123
793 1634
1315 573
573 816
1123 1821
1532 1123
2 793
789 793
1315 896
1315 596
816 590
945 816
1821 1839
1867 1821
1590 1532
1532 633
1632 2
1943 2
611 789
789 1210
896 811
896 1142
596 1551
596 1328
590 1891
505 59...

output:

3841

result:

ok single line: '3841'

Test #81:

score: 0
Accepted
time: 0ms
memory: 18432kb

input:

2000 992
1 2 7 13 15 16 20 21 23 24 25 26 27 28 30 31 33 37 38 41 43 45 49 55 63 64 66 68 69 72 74 75 76 77 79 82 83 85 88 89 90 94 96 98 99 101 102 103 104 107 108 109 110 112 114 116 121 122 125 130 131 133 136 139 140 141 143 148 152 154 156 157 158 165 166 168 171 177 179 181 182 183 186 188 189...

output:

1008

result:

ok single line: '1008'

Test #82:

score: 0
Accepted
time: 0ms
memory: 20324kb

input:

2000 1
1163
1348 1163
1163 1417
1348 1066
691 1348
1417 1063
1824 1417
690 1066
1066 1128
85 691
1457 691
1963 1063
1063 11
207 1824
885 1824
690 1531
690 1349
550 1128
612 1128
1134 85
338 85
1536 1457
1457 678
1963 643
1963 616
11 1526
11 1347
749 207
1658 207
885 1927
238 885
1531 522
1863 1531
1...

output:

3988

result:

ok single line: '3988'

Test #83:

score: 0
Accepted
time: 0ms
memory: 17836kb

input:

2000 25
57 249 324 334 468 608 658 676 861 1090 1096 1218 1223 1334 1360 1394 1563 1680 1698 1706 1728 1738 1770 1787 1921
368 85
368 829
1933 368
368 1810
97 368
624 368
1998 368
696 368
1554 368
644 368
1893 368
368 981
1373 368
368 501
1846 368
1063 368
368 342
368 1119
368 1229
368 1869
368 1574...

output:

3948

result:

ok single line: '3948'

Test #84:

score: 0
Accepted
time: 0ms
memory: 16880kb

input:

2000 1987
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

25

result:

ok single line: '25'

Test #85:

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

input:

2000 1
1948
1609 1948
938 1948
365 1948
1948 795
355 1948
1215 1948
1422 1948
1948 1006
1948 1980
1948 1985
1948 334
1948 1505
1948 965
943 1948
1863 1948
1365 1948
313 1948
1948 9
865 1948
1948 540
307 1948
400 1948
1948 787
1948 363
1806 1948
1640 1948
1725 1948
1116 1948
1149 1948
1948 1295
1948 ...

output:

3997

result:

ok single line: '3997'

Test #86:

score: 0
Accepted
time: 0ms
memory: 18228kb

input:

2000 16
169 238 361 520 526 620 631 780 791 943 996 1174 1239 1675 1841 1942
831 1120
1120 128
128 1464
128 69
1773 69
1068 1464
1016 1120
419 1068
1967 1120
1120 1805
1805 345
1959 128
331 1959
12 1016
1959 1197
345 633
345 1660
1197 513
1463 1959
380 513
1601 1660
1660 897
1660 1914
1215 380
1601 ...

output:

3437

result:

ok single line: '3437'

Test #87:

score: 0
Accepted
time: 4ms
memory: 16852kb

input:

2000 1982
1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

output:

18

result:

ok single line: '18'

Test #88:

score: 0
Accepted
time: 2ms
memory: 17868kb

input:

2000 7
57 568 1115 1440 1834 1893 1964
1264 1086
1086 1386
45 1264
45 325
1214 1086
582 45
1200 1086
230 1386
1463 1214
759 1200
1386 1452
325 469
1452 951
1214 468
469 1189
1452 56
1463 1254
1452 2000
759 1932
395 1189
56 772
1886 56
1886 679
1442 56
1220 1189
1220 1830
1711 1830
2000 1561
1502 156...

output:

3559

result:

ok single line: '3559'

Test #89:

score: 0
Accepted
time: 0ms
memory: 17288kb

input:

2000 688
2 4 5 7 13 25 30 34 35 36 39 43 45 48 54 63 65 66 67 68 69 77 80 81 84 85 86 89 91 93 104 106 108 112 114 115 121 124 127 130 134 135 137 138 140 144 145 146 147 149 151 154 157 158 159 160 161 167 168 169 174 176 181 182 185 186 187 191 196 205 207 208 210 212 213 214 221 228 230 233 235 2...

output:

1312

result:

ok single line: '1312'

Test #90:

score: 0
Accepted
time: 0ms
memory: 17556kb

input:

2000 21
10 53 98 299 380 427 532 560 606 776 1054 1216 1247 1270 1312 1343 1385 1421 1792 1796 1884
570 675
570 1087
926 570
1989 926
1087 721
493 926
1100 926
1110 675
721 1767
1989 1696
1558 1087
570 1283
1694 570
1283 320
438 570
1194 1694
721 558
1041 1696
625 1110
1110 1318
1597 1041
625 1415
8...

output:

3744

result:

ok single line: '3744'

Test #91:

score: 0
Accepted
time: 0ms
memory: 18348kb

input:

2000 1986
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

14

result:

ok single line: '14'

Test #92:

score: 0
Accepted
time: 0ms
memory: 18036kb

input:

2000 10
28 418 931 934 1240 1503 1643 1707 1724 1753
1931 1583
621 1931
1931 124
1583 353
320 353
621 543
447 543
124 111
510 621
624 621
111 1086
728 510
1519 124
1818 1931
1153 1818
1450 1583
400 111
111 198
587 320
845 1931
1778 1086
1086 894
702 894
1163 894
882 894
1871 111
111 1952
624 1925
11...

output:

3862

result:

ok single line: '3862'

Test #93:

score: 0
Accepted
time: 0ms
memory: 17200kb

input:

2000 959
1 5 6 9 12 13 14 19 23 27 29 32 33 35 36 37 38 39 40 41 44 46 50 53 55 56 57 60 63 67 68 69 71 72 73 75 76 77 79 80 82 83 84 85 86 87 89 91 92 93 94 96 97 98 99 100 102 104 107 108 109 110 111 114 118 123 125 127 128 130 132 138 139 142 146 147 148 149 150 152 153 154 156 157 159 163 165 16...

output:

1041

result:

ok single line: '1041'

Test #94:

score: 0
Accepted
time: 0ms
memory: 16672kb

input:

1998 23
3 92 105 119 164 169 188 269 343 394 489 700 741 981 1092 1317 1441 1525 1693 1811 1878 1896 1989
1653 1791
1791 1250
1300 277
600 277
277 1791
447 1635
1282 1635
1635 277
1251 542
1251 532
1251 1635
526 1739
1379 1739
1251 1739
240 1090
1607 1090
1090 1739
1784 1927
101 1927
1090 1927
1006 ...

output:

3267

result:

ok single line: '3267'

Test #95:

score: 0
Accepted
time: 0ms
memory: 18084kb

input:

1998 1977
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

21

result:

ok single line: '21'

Test #96:

score: 0
Accepted
time: 0ms
memory: 17172kb

input:

1998 18
211 319 683 783 800 878 926 969 1001 1184 1297 1407 1654 1678 1766 1785 1789 1929
1287 1709
1379 1287
670 1987
670 300
1287 670
1338 1778
1338 1479
670 1338
1809 1226
213 1809
1338 1809
543 1817
109 1817
1817 1809
1205 1132
1132 85
1817 1132
994 1315
994 425
994 1132
102 1973
980 1973
994 19...

output:

3277

result:

ok single line: '3277'

Test #97:

score: 0
Accepted
time: 0ms
memory: 17956kb

input:

1998 1322
1 2 3 4 5 7 11 12 14 16 17 18 20 21 22 25 26 27 30 31 32 33 34 35 37 38 40 41 42 43 44 47 48 49 50 51 53 54 55 56 58 59 60 62 66 67 68 69 71 72 73 74 77 78 79 82 83 85 86 87 89 90 91 92 95 96 97 98 99 100 101 103 104 105 106 108 109 111 112 113 114 115 116 117 118 119 120 122 123 124 126 1...

output:

676

result:

ok single line: '676'

Test #98:

score: 0
Accepted
time: 0ms
memory: 17448kb

input:

1998 1
627
859 627
627 579
744 1790
484 744
627 744
1436 481
1267 1436
1436 744
1461 243
1830 243
1436 243
1225 1346
1346 935
243 1346
1294 821
1294 296
1346 1294
1661 11
1895 11
1294 11
1381 192
557 1381
11 1381
679 997
1179 997
997 1381
1323 422
422 1177
997 422
696 713
713 900
422 713
1733 70
173...

output:

3328

result:

ok single line: '3328'

Test #99:

score: 0
Accepted
time: 0ms
memory: 17680kb

input:

2000 14
3 357 791 843 895 1074 1123 1156 1223 1364 1398 1522 1648 1872
214 967
1157 967
1897 967
967 1716
1361 967
667 967
967 27
967 1629
967 400
967 1555
967 617
967 166
967 435
631 967
357 967
1564 967
930 967
735 967
807 967
625 967
713 967
1091 967
374 967
799 967
967 1601
675 967
967 1834
55 9...

output:

3949

result:

ok single line: '3949'

Test #100:

score: 0
Accepted
time: 0ms
memory: 16848kb

input:

2000 1977
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 96 97 98 99 100 1...

output:

27

result:

ok single line: '27'

Test #101:

score: 0
Accepted
time: 0ms
memory: 16728kb

input:

2000 19
28 80 101 136 189 270 422 497 835 846 889 1022 1086 1117 1225 1392 1619 1787 1861
1981 940
940 1615
940 1235
451 940
1465 940
940 1648
940 163
940 1218
940 1283
1059 940
808 940
756 940
940 237
1145 940
823 940
1727 940
232 940
797 940
940 899
940 245
940 699
790 940
940 765
1016 940
940 78
...

output:

3931

result:

ok single line: '3931'

Test #102:

score: 0
Accepted
time: 4ms
memory: 18516kb

input:

2000 1932
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

output:

70

result:

ok single line: '70'

Test #103:

score: 0
Accepted
time: 0ms
memory: 17572kb

input:

2000 1
718
718 1576
718 1840
718 1103
1682 718
181 718
718 1057
718 556
1096 718
718 737
1770 718
1750 718
1759 718
718 504
718 1599
718 210
718 348
1895 718
718 1414
731 718
1904 718
718 1328
718 1053
457 718
1346 718
718 1169
718 453
718 1749
674 718
718 297
1505 718
718 801
718 189
1920 718
718 1...

output:

3996

result:

ok single line: '3996'

Test #104:

score: 0
Accepted
time: 4ms
memory: 16904kb

input:

2000 2
530 1450
530 1863
665 1863
665 473
979 473
979 1873
1873 1722
51 1722
326 51
326 1340
1340 166
1933 166
1933 1825
1825 737
1460 737
1460 861
861 1728
1728 1534
1453 1534
1374 1453
467 1374
1716 467
1716 936
936 1285
147 1285
147 790
790 233
233 1071
1444 1071
1444 1679
1679 265
232 265
232 91...

output:

2990

result:

ok single line: '2990'

Test #105:

score: 0
Accepted
time: 4ms
memory: 17604kb

input:

2000 2
1188 1685
1685 473
1683 473
992 1683
966 992
128 966
128 315
315 1201
1273 1201
1726 1273
1695 1726
1360 1695
701 1360
701 1228
589 1228
589 1141
1141 1641
734 1641
1235 734
837 1235
600 837
1339 600
1339 1910
1910 365
1261 365
1261 1526
555 1526
1210 555
1456 1210
1456 858
858 1263
367 1263
...

output:

3769

result:

ok single line: '3769'

Test #106:

score: 0
Accepted
time: 2ms
memory: 17944kb

input:

2000 1
719
322 719
322 207
307 207
1057 307
1057 1189
1189 1029
1029 1850
1850 841
841 1535
1535 1628
362 1628
1971 362
1971 956
783 956
421 783
421 1279
1279 1217
602 1217
602 1151
1151 717
717 599
599 598
598 1094
1094 1136
1136 282
678 282
678 1492
1492 181
673 181
1392 673
281 1392
1300 281
1386...

output:

1999

result:

ok single line: '1999'

Test #107:

score: 0
Accepted
time: 2ms
memory: 17752kb

input:

2000 1
1151
582 1568
582 292
1787 1568
1079 1568
112 1787
1563 1568
1568 640
218 1079
112 1561
1664 1563
1529 1664
1664 554
297 1079
1529 1381
1529 821
332 582
1563 1369
821 1704
1664 1685
1704 516
292 1299
1787 1033
1299 1229
1741 1561
355 1787
620 1033
1563 1818
369 112
784 1568
1529 1081
958 1381...

output:

3981

result:

ok single line: '3981'

Test #108:

score: 0
Accepted
time: 0ms
memory: 18480kb

input:

2000 2000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

0

result:

ok single line: '0'

Subtask #4:

score: 10
Accepted

Test #109:

score: 10
Accepted
time: 27ms
memory: 41024kb

input:

500000 1
1
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:

999997

result:

ok single line: '999997'

Test #110:

score: 0
Accepted
time: 155ms
memory: 63572kb

input:

500000 1
60670
416113 399488
399488 351393
122946 351393
122946 189103
189103 324384
324384 193737
50197 193737
50197 1032
1032 55722
11116 55722
11116 434203
434203 204486
487376 204486
487376 286003
286003 82640
131436 82640
131436 84536
84536 382871
382871 353225
32866 353225
32866 93733
93733 28...

output:

623920

result:

ok single line: '623920'

Test #111:

score: 0
Accepted
time: 166ms
memory: 60052kb

input:

500000 1
51661
403957 51661
38280 403957
83357 38280
343955 83357
71505 343955
71505 410956
153670 410956
430944 153670
6068 430944
6068 344062
246391 344062
108815 246391
108815 195295
287311 195295
130936 287311
130936 456905
186224 456905
217604 186224
384570 217604
370993 384570
121339 370993
12...

output:

499999

result:

ok single line: '499999'

Test #112:

score: 0
Accepted
time: 143ms
memory: 39920kb

input:

500000 1
142108
79960 117197
117197 271776
79960 493880
79960 226748
485452 271776
271776 100348
11256 493880
33785 493880
226748 214375
255142 226748
367533 485452
469119 485452
100348 256544
287618 100348
11256 66143
146481 11256
33785 454765
33785 461263
214375 405630
436727 214375
343283 255142
...

output:

999962

result:

ok single line: '999962'

Test #113:

score: 0
Accepted
time: 132ms
memory: 39880kb

input:

500000 1
23292
23292 212764
23292 124709
436774 212764
339491 212764
343274 124709
124709 433322
221393 436774
436774 140970
337414 339491
339491 347017
250469 343274
238154 343274
116574 433322
424979 433322
221393 37613
221393 216488
252895 140970
140970 438459
337414 440055
120545 337414
347017 4...

output:

999980

result:

ok single line: '999980'

Test #114:

score: 0
Accepted
time: 112ms
memory: 41112kb

input:

500000 1
367454
217963 169721
188797 217963
217963 306059
217963 50478
217963 68555
217963 108315
247734 217963
217963 204376
217963 474301
215535 217963
217963 497173
217963 332140
217963 29088
217963 415378
217963 376317
343010 217963
60295 217963
266741 217963
213010 217963
217963 406769
217963 1...

output:

999996

result:

ok single line: '999996'

Test #115:

score: 0
Accepted
time: 118ms
memory: 41464kb

input:

500000 1
421879
421879 455663
110929 421879
421879 48723
439356 421879
437852 421879
421879 461962
351562 421879
117604 421879
145183 421879
421879 350826
421879 411786
421879 499216
378970 421879
421879 205316
421879 128310
313393 421879
421879 43304
421879 483785
421879 144751
421879 190443
421879...

output:

999997

result:

ok single line: '999997'

Test #116:

score: 0
Accepted
time: 201ms
memory: 40404kb

input:

500000 1
110399
51226 290058
197044 290058
155601 290058
152640 290058
155601 266299
242807 197044
136207 51226
290058 234521
266299 366716
87626 136207
392225 51226
136207 415345
366716 166712
43639 290058
116294 51226
290058 291526
152640 457008
234521 394100
433386 136207
234521 490862
87626 1231...

output:

999961

result:

ok single line: '999961'

Test #117:

score: 0
Accepted
time: 158ms
memory: 42828kb

input:

500000 1
441553
103964 441553
20014 441553
441553 355589
180155 441553
441553 86367
441553 382668
441553 210402
441553 324944
441553 338460
441553 456619
441553 216986
356316 441553
179327 441553
365278 441553
441553 483160
441553 20662
77630 441553
441553 187973
441553 327168
441553 311570
433996 4...

output:

999996

result:

ok single line: '999996'

Test #118:

score: 0
Accepted
time: 185ms
memory: 74008kb

input:

500000 1
235661
296222 370563
370563 103471
421352 103471
215756 421352
62943 215756
166029 62943
166029 112172
112172 45325
136951 45325
136951 164561
41743 164561
41743 64497
64497 292093
120875 292093
120875 465620
413798 465620
355618 413798
355618 138067
413536 138067
413536 118711
70948 118711...

output:

690532

result:

ok single line: '690532'

Test #119:

score: 0
Accepted
time: 163ms
memory: 78776kb

input:

500000 1
324927
148943 324927
83974 148943
88612 83974
27247 88612
215964 27247
296037 215964
202911 296037
272028 202911
272028 489615
489615 378258
403316 378258
422854 403316
124803 422854
465473 124803
99481 465473
99481 386621
194254 386621
182382 194254
165171 182382
278377 165171
54832 278377...

output:

499999

result:

ok single line: '499999'

Test #120:

score: 0
Accepted
time: 154ms
memory: 39952kb

input:

500000 1
334612
334612 158651
334612 79238
158651 274820
158651 281792
79238 361686
371343 79238
274820 247983
237664 274820
281792 490742
165667 281792
361686 237634
361686 337096
371343 137547
371343 356009
247983 224323
167055 247983
231744 237664
237664 305338
490742 456477
51685 490742
165667 1...

output:

999980

result:

ok single line: '999980'

Test #121:

score: 0
Accepted
time: 98ms
memory: 41248kb

input:

500000 1
74974
482196 74974
51123 74974
74974 465710
326199 74974
137963 74974
419142 74974
384717 74974
393594 74974
74974 151126
481926 74974
74974 269865
373392 74974
74974 100651
74974 100236
74974 246690
320333 74974
74974 227136
74974 79338
74974 281570
368034 74974
474671 74974
74974 264830
7...

output:

999997

result:

ok single line: '999997'

Test #122:

score: 0
Accepted
time: 130ms
memory: 51532kb

input:

499998 1
496222
496222 253474
496222 334636
231903 476964
476964 455588
496222 476964
297907 142966
297907 495353
297907 476964
94866 44431
94866 353347
94866 297907
237183 54871
295805 54871
54871 94866
255119 396158
90781 255119
54871 255119
375072 366021
339547 366021
366021 255119
186927 245117
...

output:

833328

result:

ok single line: '833328'

Test #123:

score: 0
Accepted
time: 159ms
memory: 42852kb

input:

500000 1
249538
287331 249538
249538 24803
427370 249538
297651 249538
249538 62967
249538 483260
496634 249538
249538 336951
249538 455667
211177 249538
249538 435090
249538 399899
266084 249538
144874 249538
249538 227113
334927 249538
249538 389446
249538 263960
138184 249538
297819 249538
279738...

output:

999996

result:

ok single line: '999996'

Test #124:

score: 0
Accepted
time: 136ms
memory: 40600kb

input:

500000 1
480529
245530 153153
245530 151340
151340 85979
151340 69972
69972 75248
357753 85979
85979 24027
245530 218462
24027 216305
211105 85979
58047 151340
218462 143494
218462 415250
220405 85979
488621 153153
488621 289003
75248 32516
220405 66306
196700 220405
75248 118668
26246 216305
214303...

output:

999961

result:

ok single line: '999961'

Subtask #5:

score: 7
Accepted

Dependency #4:

100%
Accepted

Test #125:

score: 7
Accepted
time: 54ms
memory: 79044kb

input:

500000 2
1 500000
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...

output:

499998

result:

ok single line: '499998'

Test #126:

score: 0
Accepted
time: 127ms
memory: 60804kb

input:

500000 2
208296 433255
433255 208296
208296 159985
159985 410957
299100 410957
299100 334053
334053 403495
403495 9812
149169 9812
149169 361250
489904 361250
489904 371995
89094 371995
218151 89094
218151 85386
85386 55410
55410 51391
51391 344784
432376 344784
432376 251862
251862 401805
121144 40...

output:

499998

result:

ok single line: '499998'

Test #127:

score: 0
Accepted
time: 115ms
memory: 62996kb

input:

500000 2
388942 488798
388942 416859
488798 416859
353081 488798
353081 11307
55130 11307
256159 55130
102611 256159
102611 123369
123369 220854
123910 220854
123910 374385
330360 374385
212190 330360
212190 237528
488296 237528
488296 390625
390625 22047
97124 22047
390511 97124
390511 495182
15678...

output:

499998

result:

ok single line: '499998'

Test #128:

score: 0
Accepted
time: 114ms
memory: 74652kb

input:

500000 2
152141 155599
152141 191739
152141 155599
155599 343417
343417 100490
100490 141758
363428 141758
150250 363428
150250 56477
56477 452739
452739 452703
452703 396184
251170 396184
401214 251170
422070 401214
303443 422070
165156 303443
433111 165156
433111 303331
132573 303331
233996 132573...

output:

499998

result:

ok single line: '499998'

Test #129:

score: 0
Accepted
time: 128ms
memory: 76192kb

input:

500000 2
16428 131762
33201 131762
407039 33201
346722 407039
346722 103442
103442 73540
135210 73540
135210 239290
239290 69574
69574 71079
71079 290636
290636 199868
199868 130301
109785 130301
109785 343754
487195 343754
386603 487195
386603 235645
236358 235645
236358 245882
221508 245882
226158...

output:

499998

result:

ok single line: '499998'

Test #130:

score: 0
Accepted
time: 127ms
memory: 67284kb

input:

500000 2
451784 461172
413494 92064
92064 91742
227803 91742
227803 56646
382741 56646
382741 255916
255916 272171
199383 272171
454531 199383
42172 454531
33957 42172
33957 385320
385320 76619
157244 76619
157244 239102
239102 497969
456456 497969
456456 336257
15346 336257
278810 15346
278810 1751...

output:

652633

result:

ok single line: '652633'

Test #131:

score: 0
Accepted
time: 99ms
memory: 47640kb

input:

499998 2
87521 456929
271418 151859
151859 135323
111680 104706
104706 291414
151859 104706
15636 479140
185103 15636
104706 15636
470099 16617
470099 216620
470099 15636
98155 49140
249251 49140
470099 49140
111806 27714
27714 238201
27714 49140
311420 289134
289134 56620
27714 289134
273202 30258
...

output:

857511

result:

ok single line: '857511'

Test #132:

score: 0
Accepted
time: 84ms
memory: 51520kb

input:

499998 2
40965 267999
40965 350687
346530 40965
366483 378932
321381 366483
40965 366483
102618 472300
291695 102618
102618 366483
171209 312811
312811 398804
102618 312811
79730 428806
258747 79730
79730 312811
35680 484730
453861 484730
79730 484730
155416 262585
262585 1087
262585 484730
298899 1...

output:

833325

result:

ok single line: '833325'

Test #133:

score: 0
Accepted
time: 158ms
memory: 57168kb

input:

500000 2
308764 327783
306101 308764
16720 306101
16720 53921
53921 116688
239454 116688
40724 239454
30482 40724
444340 30482
19782 444340
19782 26166
26166 5652
447184 5652
447184 369414
171610 369414
171610 175244
34841 175244
51289 34841
346613 51289
346613 161890
140966 161890
140966 149643
149...

output:

749986

result:

ok single line: '749986'

Test #134:

score: 0
Accepted
time: 167ms
memory: 40020kb

input:

500000 2
62556 479631
62556 19046
195054 19046
195054 250073
17577 250073
68274 17577
68274 239610
239610 359814
60862 359814
60862 52118
234439 52118
479857 234439
479857 481787
370534 481787
370534 166994
456657 166994
449101 456657
432684 449101
76702 432684
464079 76702
464079 222972
217773 2229...

output:

997358

result:

ok single line: '997358'

Test #135:

score: 0
Accepted
time: 133ms
memory: 45688kb

input:

500000 2
52546 468448
468448 64609
64609 17212
74523 17212
74523 104676
116441 104676
116441 276865
276865 478186
478186 146572
146572 52546
17212 118933
276865 498901
111675 52546
146572 192566
462990 74523
406302 498901
300627 478186
406302 333643
64609 30039
192566 65194
116441 133923
104676 1736...

output:

899761

result:

ok single line: '899761'

Test #136:

score: 0
Accepted
time: 100ms
memory: 39924kb

input:

500000 2
397125 491177
496349 137050
135385 496349
137050 445212
137050 447368
310848 135385
135385 357372
445212 431320
40598 445212
447368 245008
447368 446693
454656 310848
76251 310848
38187 357372
69613 357372
228153 431320
490436 431320
320562 40598
40598 97232
330231 245008
499 245008
352270 ...

output:

999931

result:

ok single line: '999931'

Test #137:

score: 0
Accepted
time: 74ms
memory: 41272kb

input:

500000 2
190963 385446
190963 385446
269404 190963
190963 220169
190963 150362
305273 190963
190963 298413
356788 190963
200771 190963
190963 119240
36653 190963
190963 212062
190963 428175
186679 190963
499539 190963
190963 407506
365966 190963
498545 190963
190963 294119
448520 190963
55996 190963...

output:

999995

result:

ok single line: '999995'

Test #138:

score: 0
Accepted
time: 100ms
memory: 45912kb

input:

500000 2
397629 460186
227370 49378
362606 227370
264644 49378
397889 49378
362606 370624
370624 50531
264644 186741
365464 227370
227370 241182
264644 196168
257613 264644
196168 108954
370906 108954
111451 365464
358294 186741
186741 170371
358294 344205
290005 196168
344205 75280
128777 75280
290...

output:

909356

result:

ok single line: '909356'

Test #139:

score: 0
Accepted
time: 125ms
memory: 40472kb

input:

500000 2
176524 352839
388024 111810
111810 270807
429256 388024
270807 331153
244215 388024
270807 422415
433726 331153
244215 352502
429256 440257
374770 440257
331153 232951
244215 267504
197949 440257
480131 374770
354377 197949
374770 235094
472632 235094
258167 197949
440257 11900
461417 42925...

output:

999920

result:

ok single line: '999920'

Test #140:

score: 0
Accepted
time: 111ms
memory: 42892kb

input:

500000 2
3239 433364
4722 1887
1887 20684
450686 1887
1887 392533
1887 280677
444210 1887
145964 1887
1887 62023
338569 1887
1887 113085
1887 264365
64564 1887
1887 342606
1887 218762
452996 1887
375461 1887
1887 53414
475965 1887
100250 1887
1887 246559
1887 239333
376901 1887
1887 35619
1887 24701...

output:

999990

result:

ok single line: '999990'

Test #141:

score: 0
Accepted
time: 114ms
memory: 62384kb

input:

500000 2
254506 275795
275795 254506
494489 254506
361537 494489
361537 288401
275605 288401
291610 275605
11452 291610
11452 204457
286326 204457
402430 286326
314066 402430
298288 314066
456008 298288
486026 456008
486026 360278
431472 360278
327765 431472
327765 193492
193492 211444
479440 211444...

output:

499998

result:

ok single line: '499998'

Test #142:

score: 0
Accepted
time: 116ms
memory: 59576kb

input:

500000 2
50349 453531
453531 342860
50349 342860
80013 50349
400494 80013
363390 400494
363390 158002
158002 331861
165184 331861
165184 335018
285442 335018
285442 137520
84589 137520
84589 233703
233703 18473
18473 337307
280293 337307
471364 280293
334505 471364
194806 334505
194806 373307
373307...

output:

499998

result:

ok single line: '499998'

Test #143:

score: 0
Accepted
time: 105ms
memory: 75756kb

input:

500000 2
295946 337068
337068 326824
295946 337068
360211 295946
360211 32115
32115 340301
184489 340301
184489 206516
464109 206516
443872 464109
281519 443872
413030 281519
413030 392901
351492 392901
351492 59043
378492 59043
361126 378492
236615 361126
127860 236615
334880 127860
94272 334880
94...

output:

499998

result:

ok single line: '499998'

Test #144:

score: 0
Accepted
time: 122ms
memory: 74464kb

input:

500000 2
151939 167620
167620 462605
462605 381744
381744 286061
427 286061
165626 427
381836 165626
128212 381836
117764 128212
117764 462737
462737 435338
435338 444628
85846 444628
85846 476469
476469 289068
289068 228773
55400 228773
342076 55400
342076 2395
293932 2395
435513 293932
235347 4355...

output:

499998

result:

ok single line: '499998'

Test #145:

score: 0
Accepted
time: 99ms
memory: 70888kb

input:

500000 2
191191 408365
460836 392393
392393 98709
98709 177434
177434 71707
273550 71707
350223 273550
61689 350223
230362 61689
466029 230362
218259 466029
218259 130460
191779 130460
191779 176168
496475 176168
496475 248671
248671 20143
418502 20143
418502 287567
309296 287567
309296 350907
35002...

output:

539175

result:

ok single line: '539175'

Test #146:

score: 0
Accepted
time: 111ms
memory: 70480kb

input:

500000 2
3014 428496
428496 196428
196428 186805
186805 79929
56105 79929
71197 56105
71197 127578
195052 127578
130244 195052
336275 130244
336275 199263
95063 199263
95063 182060
408666 182060
331364 408666
120917 331364
361404 120917
361404 262932
268500 262932
268500 439298
40225 439298
166192 4...

output:

499998

result:

ok single line: '499998'

Test #147:

score: 0
Accepted
time: 112ms
memory: 73864kb

input:

500000 2
174342 491121
491121 174342
430465 491121
430465 109851
407871 109851
463854 407871
31547 463854
165915 31547
337687 165915
337687 150217
150217 335235
123906 335235
123906 143472
305683 143472
305683 290495
290495 272166
46544 272166
58626 46544
58626 465640
465640 169245
387267 169245
387...

output:

499998

result:

ok single line: '499998'

Test #148:

score: 0
Accepted
time: 176ms
memory: 58592kb

input:

500000 2
185055 321482
185055 430786
430786 245588
210763 245588
210763 361593
80769 361593
221993 80769
221993 2343
251398 2343
251398 137602
137602 211166
211166 270004
270004 110363
110363 159636
159636 409728
381555 409728
381555 216911
139570 216911
139570 378439
378439 428305
428305 139597
316...

output:

749988

result:

ok single line: '749988'

Test #149:

score: 0
Accepted
time: 160ms
memory: 42888kb

input:

500000 2
398133 431090
21913 431090
21913 34920
34920 260413
260413 203169
203169 66203
66203 82078
240308 82078
240308 303333
303333 33794
472000 33794
472000 232082
232082 473974
473974 206265
87170 206265
90678 87170
90678 316725
316725 437846
125450 437846
326806 125450
267256 326806
267256 1607...

output:

949959

result:

ok single line: '949959'

Test #150:

score: 0
Accepted
time: 149ms
memory: 44528kb

input:

500000 2
370539 450164
97019 450164
97019 245503
245503 211872
211872 50769
50769 166651
62441 166651
62441 12414
12414 455710
370539 455710
369418 370539
97019 306574
166651 237052
155063 12414
237052 111745
18819 155063
306807 18819
50769 309790
306807 103934
229923 450164
455710 175785
245503 341...

output:

899467

result:

ok single line: '899467'

Subtask #6:

score: 7
Accepted

Test #151:

score: 7
Accepted
time: 124ms
memory: 72388kb

input:

500000 11
14094 127994 130392 141985 162219 173658 265993 279756 320282 326005 400597
272490 213695
392437 272490
98667 392437
98667 359150
150533 359150
150533 435047
419401 435047
61283 419401
18028 61283
483952 18028
380301 483952
380301 246367
246367 91867
91867 106190
106190 493451
207050 49345...

output:

501449

result:

ok single line: '501449'

Test #152:

score: 0
Accepted
time: 177ms
memory: 73996kb

input:

500000 499990
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

10

result:

ok single line: '10'

Test #153:

score: 0
Accepted
time: 109ms
memory: 73592kb

input:

500000 13
3494 26344 27346 124946 167417 279360 302702 304872 329686 336086 394825 410349 420265
48951 267602
267602 496123
24096 496123
24096 234099
234099 34813
174951 34813
161897 174951
414563 161897
346100 414563
346100 86361
86361 70501
6392 70501
401308 6392
401308 240475
240475 323454
415438...

output:

510426

result:

ok single line: '510426'

Test #154:

score: 0
Accepted
time: 124ms
memory: 66776kb

input:

500000 499995
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

5

result:

ok single line: '5'

Subtask #7:

score: 30
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 #155:

score: 30
Accepted
time: 85ms
memory: 39852kb

input:

500000 14
656 6179 32297 63781 77539 85222 138761 165987 193535 232431 262922 263542 336091 479023
72964 113860
298150 113860
72964 406032
226375 72964
298150 178168
298150 258060
133577 406032
406032 361109
226375 222375
226375 212496
178168 319378
284495 178168
461817 258060
12715 258060
133577 36...

output:

999603

result:

ok single line: '999603'

Test #156:

score: 0
Accepted
time: 95ms
memory: 39868kb

input:

500000 499990
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

10

result:

ok single line: '10'

Test #157:

score: 0
Accepted
time: 112ms
memory: 39928kb

input:

500000 4
62293 284835 479228 490301
489725 196712
489725 10658
197399 196712
196712 41478
818 10658
10658 67451
197399 8934
197399 456607
41478 499434
41478 106131
818 403730
818 390513
68925 67451
67451 296347
8934 170312
158031 8934
456607 108995
456607 353340
499434 276615
499434 303090
106131 48...

output:

999864

result:

ok single line: '999864'

Test #158:

score: 0
Accepted
time: 83ms
memory: 39864kb

input:

500000 249996
3 4 6 7 8 9 10 12 16 17 19 24 29 32 33 34 35 36 37 40 42 44 45 50 52 55 56 57 60 62 63 66 67 69 70 71 72 73 74 75 77 78 86 87 92 97 99 101 103 104 105 106 107 108 109 113 114 115 120 121 122 123 126 127 128 130 131 134 135 136 137 141 142 148 149 150 151 154 155 156 157 158 160 162 163...

output:

250004

result:

ok single line: '250004'

Test #159:

score: 0
Accepted
time: 75ms
memory: 41232kb

input:

500000 9
55998 80630 164192 170399 179294 202307 278785 335676 392961
393544 264955
264955 313515
251289 264955
127473 264955
28321 264955
496 264955
264955 150033
264955 81141
305636 264955
264955 36513
472397 264955
22130 264955
264955 250328
92172 264955
187782 264955
239317 264955
264955 200755
...

output:

999980

result:

ok single line: '999980'

Test #160:

score: 0
Accepted
time: 87ms
memory: 41188kb

input:

500000 499995
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

9

result:

ok single line: '9'

Test #161:

score: 0
Accepted
time: 133ms
memory: 45136kb

input:

500000 8
30500 96925 243576 284843 302409 364086 464307 488608
309042 123990
331043 309042
331043 466617
375740 466617
485054 375740
67522 375740
331043 244469
167739 375740
87754 67522
58464 309042
485054 43319
21116 167739
395493 21116
485054 167389
58464 264895
67522 210904
167389 388268
264895 2...

output:

908984

result:

ok single line: '908984'

Test #162:

score: 0
Accepted
time: 135ms
memory: 44956kb

input:

500000 499990
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

10

result:

ok single line: '10'

Test #163:

score: 0
Accepted
time: 114ms
memory: 45272kb

input:

500000 3
179070 203709 484006
214882 240611
214882 431682
214882 400700
431682 363524
400700 161947
431682 237605
188285 161947
404699 240611
473745 240611
431682 79945
322440 404699
346810 400700
454531 161947
404699 436070
398975 161947
340066 188285
188285 458385
473745 493451
346810 499522
49952...

output:

913746

result:

ok single line: '913746'

Test #164:

score: 0
Accepted
time: 142ms
memory: 44472kb

input:

500000 174783
4 5 10 13 14 17 18 19 20 22 24 30 31 33 36 39 42 43 48 52 56 57 65 74 75 76 82 87 88 91 97 98 99 104 107 112 113 114 115 119 120 129 130 131 133 134 136 138 142 146 149 151 154 156 158 163 165 167 171 175 178 180 184 187 188 192 194 196 197 198 204 207 208 214 218 219 221 226 227 228 2...

output:

325217

result:

ok single line: '325217'

Test #165:

score: 0
Accepted
time: 166ms
memory: 40440kb

input:

500000 12
95925 112883 159161 200502 252798 298174 338993 375634 382408 410409 476704 485236
298408 388372
298408 25322
25322 56438
388372 241642
298408 258144
164337 241642
164337 259445
365522 25322
164337 429699
114959 258144
267274 388372
490136 56438
298408 53972
327120 258144
428896 241642
336...

output:

999597

result:

ok single line: '999597'

Test #166:

score: 0
Accepted
time: 182ms
memory: 40432kb

input:

500000 499989
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

11

result:

ok single line: '11'

Test #167:

score: 0
Accepted
time: 157ms
memory: 40604kb

input:

500000 7
12114 35512 114197 226634 231994 413322 431557
496852 29601
496852 460649
276148 29601
29601 393970
393970 158580
460649 292096
393970 268240
393970 13095
276148 145147
393970 316746
29601 65927
496852 100695
257362 158580
100695 120039
366408 257362
145147 13032
470535 65927
29601 412118
4...

output:

999770

result:

ok single line: '999770'

Test #168:

score: 0
Accepted
time: 179ms
memory: 40428kb

input:

500000 250102
1 3 6 10 13 14 18 23 24 25 26 27 32 33 34 35 41 44 46 48 49 50 51 56 57 59 60 64 66 68 69 71 72 73 75 78 82 84 86 88 90 91 94 95 98 99 101 102 104 107 108 109 110 111 112 113 115 116 118 119 120 123 125 127 129 131 135 137 139 140 141 142 143 147 149 150 154 155 157 159 160 162 163 165...

output:

249898

result:

ok single line: '249898'

Test #169:

score: 0
Accepted
time: 110ms
memory: 49496kb

input:

499998 10
57891 93348 138253 150647 248200 280919 320530 381683 383460 446894
215249 217333
217333 113540
173593 476062
173593 361992
217333 173593
161164 127597
228868 161164
173593 161164
210517 366645
366645 82927
161164 366645
287615 356730
388120 287615
366645 287615
292960 414777
292960 422514...

output:

835989

result:

ok single line: '835989'

Test #170:

score: 0
Accepted
time: 116ms
memory: 50144kb

input:

499998 499986
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

12

result:

ok single line: '12'

Test #171:

score: 0
Accepted
time: 102ms
memory: 48192kb

input:

499998 7
68043 165267 226797 231241 318049 440145 477328
124801 160919
124801 41266
460741 335950
335950 192504
335950 124801
227148 216036
227148 53410
227148 335950
240031 233568
233568 190654
233568 227148
173254 44384
173254 215067
233568 173254
459158 140812
355388 459158
173254 459158
229103 1...

output:

836902

result:

ok single line: '836902'

Test #172:

score: 0
Accepted
time: 111ms
memory: 46500kb

input:

499998 333323
1 2 3 4 5 7 8 10 12 13 14 15 16 17 18 19 20 22 24 25 27 28 29 30 31 32 33 37 38 39 43 44 48 51 53 54 55 56 58 59 60 61 62 64 65 66 67 69 70 71 72 73 75 77 78 79 83 84 85 86 89 92 93 94 95 96 97 99 100 101 104 105 106 107 108 110 111 113 114 117 118 119 120 121 122 123 124 125 126 128 1...

output:

166675

result:

ok single line: '166675'

Test #173:

score: 0
Accepted
time: 121ms
memory: 42856kb

input:

500000 14
73206 97111 98975 156481 176679 192857 233561 266246 293678 327521 379117 386225 388197 492824
210322 419112
419112 115640
170814 419112
396093 419112
419112 302772
414 419112
120814 419112
186300 419112
60505 419112
12992 419112
23216 419112
148849 419112
419112 310024
198025 419112
41911...

output:

999942

result:

ok single line: '999942'

Test #174:

score: 0
Accepted
time: 121ms
memory: 42760kb

input:

500000 499989
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

11

result:

ok single line: '11'

Test #175:

score: 0
Accepted
time: 98ms
memory: 42828kb

input:

500000 13
74212 84766 127176 230893 245310 284119 311805 332879 333884 421009 426115 490856 497746
333885 41164
333885 41051
333885 273150
333885 190682
333885 137961
333885 189481
428950 333885
333885 340539
365458 333885
498004 333885
384483 333885
40595 333885
333885 179772
333885 117884
470821 3...

output:

999946

result:

ok single line: '999946'

Test #176:

score: 0
Accepted
time: 123ms
memory: 42788kb

input:

500000 499283
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

717

result:

ok single line: '717'

Test #177:

score: 0
Accepted
time: 113ms
memory: 40416kb

input:

500000 500000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

0

result:

ok single line: '0'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-01-20 12:10:55 | OpenSource Project