UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213521#2769. 覆盖nullptr_qwq10036112ms300316kbC++115.2kb2024-11-12 19:41:202024-11-12 23:17:32

answer

// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
ll read(){
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
namespace Fastio{struct Reader{template<typename T>Reader&operator>>(T&x){x=0;short f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();x*=f;return*this;}Reader&operator>>(double&x){x=0;double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(long double&x){x=0;long double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(__float128&x){x=0;__float128 t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(char&c){c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();return*this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}Reader&operator>>(string&str){str.clear();char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{const int Setprecision=6;typedef int mxdouble;template<typename T>Writer&operator<<(T x){if(x==0){putchar('0');return*this;}if(x<0)putchar('-'),x=-x;static short sta[40];short top=0;while(x>0)sta[++top]=x%10,x/=10;while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}using namespace Fastio;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=2000005;
vector<int>g[maxn];
set<int>st[maxn];
int vis[maxn],n,m;
void dfs(int u,int fa=0){
	for(auto v:g[u])if(v^fa){
		dfs(v,u);
		if(SZ(st[u])<SZ(st[v]))swap(st[u],st[v]);
		for(auto i:st[v])if(!st[u].insert(i).second)vis[u]=1;
	}
	if(vis[u])st[u].clear();
}
void solve(){
	cin>>n;
	F(_,1,n-1){
		int u,v; cin>>u>>v;
		g[u].push_back(v),g[v].push_back(u);
	}
	cin>>m;
	F(_,1,m){
		int u,v; cin>>u>>v;
		if(u==v)vis[u]=1;
		else st[u].insert(_),st[v].insert(_);
	} dfs(1);
	int ans=0;
	F(i,1,n)ans+=vis[i];
	cout<<ans<<endl;
	F(i,1,n)if(vis[i])cout<<i<<' ';
}
signed main(){
	// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int zsy=1;
	F(____,1,zsy)solve();
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 32ms
memory: 141804kb

input:

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

output:

2
3 10 

result:

ok ok

Test #2:

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

input:

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

output:

2
6 13 

result:

ok ok

Test #3:

score: 0
Accepted
time: 34ms
memory: 141808kb

input:

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

output:

3
1 4 11 

result:

ok ok

Test #4:

score: 0
Accepted
time: 35ms
memory: 141808kb

input:

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

output:

2
5 11 

result:

ok ok

Test #5:

score: 0
Accepted
time: 31ms
memory: 141808kb

input:

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

output:

6
1 3 7 10 17 19 

result:

ok ok

Test #6:

score: 0
Accepted
time: 36ms
memory: 141804kb

input:

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

output:

3
4 9 13 

result:

ok ok

Test #7:

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

input:

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

output:

2
5 8 

result:

ok ok

Test #8:

score: 0
Accepted
time: 24ms
memory: 141808kb

input:

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

output:

2
4 10 

result:

ok ok

Test #9:

score: 0
Accepted
time: 35ms
memory: 141804kb

input:

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

output:

3
3 8 10 

result:

ok ok

Test #10:

score: 0
Accepted
time: 46ms
memory: 141808kb

input:

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

output:

2
7 12 

result:

ok ok

Subtask #2:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 44ms
memory: 141868kb

input:

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

output:

11
53 131 186 235 258 280 289 317 397 471 585 

result:

ok ok

Test #12:

score: 0
Accepted
time: 19ms
memory: 141876kb

input:

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

output:

16
96 109 110 114 152 154 179 285 315 418 463 469 526 561 610 822 

result:

ok ok

Test #13:

score: 0
Accepted
time: 23ms
memory: 141852kb

input:

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

output:

2
40 305 

result:

ok ok

Test #14:

score: 0
Accepted
time: 35ms
memory: 141872kb

input:

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

output:

15
36 77 111 161 164 218 236 277 281 391 408 410 460 577 738 

result:

ok ok

Test #15:

score: 0
Accepted
time: 20ms
memory: 141912kb

input:

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

output:

17
46 104 126 230 293 313 324 439 460 462 469 504 513 526 546 646 694 

result:

ok ok

Test #16:

score: 0
Accepted
time: 23ms
memory: 141848kb

input:

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

output:

6
18 114 168 201 311 651 

result:

ok ok

Test #17:

score: 0
Accepted
time: 20ms
memory: 141884kb

input:

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

output:

16
11 42 68 113 171 249 311 341 361 373 423 450 497 567 586 649 

result:

ok ok

Test #18:

score: 0
Accepted
time: 23ms
memory: 141844kb

input:

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

output:

4
15 167 387 437 

result:

ok ok

Test #19:

score: 0
Accepted
time: 23ms
memory: 141856kb

input:

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

output:

10
33 158 210 236 363 364 367 372 873 978 

result:

ok ok

Test #20:

score: 0
Accepted
time: 35ms
memory: 141848kb

input:

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

output:

5
7 85 118 241 307 

result:

ok ok

Subtask #3:

score: 40
Accepted

Test #21:

score: 40
Accepted
time: 1027ms
memory: 205304kb

input:

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

output:

5
260 10715 16698 23494 49620 

result:

ok ok

Test #22:

score: 0
Accepted
time: 1250ms
memory: 205684kb

input:

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

output:

45
2404 7524 11229 11999 14383 16080 18852 24573 25801 31547 35420 37754 42334 58888 69242 72415 820...

result:

ok ok

Test #23:

score: 0
Accepted
time: 1108ms
memory: 218492kb

input:

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

output:

288
553 5636 9673 9795 15417 22482 28415 29113 30841 31695 36154 36370 41110 45282 46034 47993 48884...

result:

ok ok

Test #24:

score: 0
Accepted
time: 1303ms
memory: 211280kb

input:

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

output:

172
4997 8750 17928 18489 27327 30718 32013 33965 34115 42664 44246 55789 56336 56495 57194 69263 74...

result:

ok ok

Test #25:

score: 0
Accepted
time: 1545ms
memory: 256160kb

input:

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

output:

635
969 1796 5534 7302 8367 9149 10058 10082 10729 13481 14831 15038 17852 18658 20221 22753 25477 2...

result:

ok ok

Test #26:

score: 0
Accepted
time: 1231ms
memory: 205660kb

input:

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

output:

27
5198 7509 8142 27608 34761 38220 48041 50127 56909 61117 71286 81891 86675 104143 114045 119648 1...

result:

ok ok

Test #27:

score: 0
Accepted
time: 1209ms
memory: 205220kb

input:

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

output:

6
490 3177 5695 8562 34548 83430 

result:

ok ok

Test #28:

score: 0
Accepted
time: 1089ms
memory: 213172kb

input:

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

output:

220
1404 2780 5137 10384 13852 18479 22969 35367 37404 38380 41605 44793 46628 49267 50316 54862 579...

result:

ok ok

Test #29:

score: 0
Accepted
time: 988ms
memory: 205344kb

input:

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

output:

18
2171 9580 14974 16009 28264 35966 39104 40324 45067 52501 56381 68915 76116 77646 77795 181356 21...

result:

ok ok

Test #30:

score: 0
Accepted
time: 1342ms
memory: 205868kb

input:

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

output:

45
2737 4251 12786 13429 14598 22080 22736 22786 25916 26716 30601 38898 40197 45646 47158 61559 631...

result:

ok ok

Test #31:

score: 0
Accepted
time: 1061ms
memory: 205852kb

input:

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

output:

32
1116 16424 21197 23111 23813 27073 27779 32582 47061 49460 49619 54106 60014 60225 61690 63492 67...

result:

ok ok

Test #32:

score: 0
Accepted
time: 1307ms
memory: 205444kb

input:

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

output:

5
5384 6708 15117 19941 80900 

result:

ok ok

Test #33:

score: 0
Accepted
time: 1255ms
memory: 205512kb

input:

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

output:

11
4421 6325 8344 16347 35897 44930 46860 57419 78545 299866 326571 

result:

ok ok

Test #34:

score: 0
Accepted
time: 951ms
memory: 205244kb

input:

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

output:

2
5187 7452 

result:

ok ok

Test #35:

score: 0
Accepted
time: 1105ms
memory: 211848kb

input:

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

output:

192
800 3704 4872 12578 14477 19995 22579 25124 29417 31207 32243 34402 42016 44099 44679 45783 4791...

result:

ok ok

Test #36:

score: 0
Accepted
time: 1255ms
memory: 237528kb

input:

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

output:

489
39 5656 7050 7487 10829 12376 13186 13483 24437 27366 29300 31447 37089 37325 41271 41767 45145 ...

result:

ok ok

Test #37:

score: 0
Accepted
time: 1061ms
memory: 205356kb

input:

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

output:

2
1572 10047 

result:

ok ok

Test #38:

score: 0
Accepted
time: 1014ms
memory: 205600kb

input:

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

output:

6
5177 16799 17244 21899 124227 342086 

result:

ok ok

Test #39:

score: 0
Accepted
time: 1083ms
memory: 205580kb

input:

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

output:

3
9574 37101 114239 

result:

ok ok

Test #40:

score: 0
Accepted
time: 1221ms
memory: 232676kb

input:

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

output:

434
2752 3375 3689 4991 6053 9618 12539 12689 13788 16278 19244 20277 22749 25323 28033 30314 36310 ...

result:

ok ok

Test #41:

score: 0
Accepted
time: 1101ms
memory: 205356kb

input:

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

output:

3
4025 12701 18588 

result:

ok ok

Test #42:

score: 0
Accepted
time: 1340ms
memory: 205904kb

input:

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

output:

46
1396 4100 10862 12634 18427 21454 23016 23231 23273 30104 38220 53924 55565 63057 75176 78809 795...

result:

ok ok

Test #43:

score: 0
Accepted
time: 1015ms
memory: 205688kb

input:

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

output:

9
7458 12356 16676 19276 29074 30431 45809 48149 71934 

result:

ok ok

Test #44:

score: 0
Accepted
time: 1016ms
memory: 205460kb

input:

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

output:

21
3775 7530 8870 10517 18085 30025 34965 42583 58317 58508 59568 71429 100130 147513 149176 154795 ...

result:

ok ok

Test #45:

score: 0
Accepted
time: 2157ms
memory: 300316kb

input:

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

output:

902
1097 2377 2384 2850 4587 8343 10511 12075 12386 12906 14030 14419 14466 16460 17707 21340 21375 ...

result:

ok ok

Test #46:

score: 0
Accepted
time: 953ms
memory: 205360kb

input:

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

output:

1
8442 

result:

ok ok

Test #47:

score: 0
Accepted
time: 1258ms
memory: 205396kb

input:

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

output:

9
5252 6422 19409 22535 24115 36225 56798 215617 409005 

result:

ok ok

Test #48:

score: 0
Accepted
time: 1013ms
memory: 205400kb

input:

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

output:

5
428 7180 7718 16350 48522 

result:

ok ok

Test #49:

score: 0
Accepted
time: 928ms
memory: 205408kb

input:

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

output:

2
1290 14389 

result:

ok ok

Test #50:

score: 0
Accepted
time: 1333ms
memory: 246108kb

input:

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

output:

559
945 1241 5644 8082 9005 9959 10848 12448 12793 14252 20587 20906 23833 27004 27886 28406 29166 3...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed