QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#623242	#8406. Alchemik Bajtazar [B]	chenxinyang2006	10 ✓	45ms	13164kb	C++20	2.1kb	2024-10-09 10:48:56	2024-10-09 10:48:56

Judging History

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

[2024-10-09 10:48:56]
评测

测评结果：10
用时：45ms
内存：13164kb

查看

[2024-10-09 10:48:56]
提交

answer

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int n,m;
vector <int> G[30005];

struct info{
	int op,u,v;
};
vector <info> ans,output;

int fa[30005];
vector <int> ord;
void dfs(int u){
	ord.eb(u);
	for(int v:G[u]){
		if(fa[v] == -1){
			fa[v] = u;
			dfs(v);
		}
	}
}

int chk(int u,int v){
	int t = lower_bound(G[u].begin(),G[u].end(),v) - G[u].begin();
	if(t < SZ(G[u]) && G[u][t] == v) return 1;
	return 0;
}

void solver(){
	rep(u,1,n) sort(G[u].begin(),G[u].end());
	fill(fa,fa + n + 1,-1);
	ord.clear();
	fa[1] = 0;
	dfs(1);
	rep(i,2,n){
		int u = ord[i - 1];
		if(!chk(1,u)) ans.push_back({1,1,u});
	}
	rep(u,2,n){
		for(int v:G[u]) if(v > u) ans.push_back({0,u,v});
	}
}

int main(){	
//	freopen("test.in","r",stdin);
	scanf("%d%d",&n,&m);
	rep(i,1,m){
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].eb(v);G[v].eb(u);
	}
	solver();
	swap(ans,output);
	rep(u,1,n) G[u].clear();
	scanf("%d",&m);
	rep(i,1,m){
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].eb(v);G[v].eb(u);
	}
	solver();
	reverse(ans.begin(),ans.end());
	for(info &I:ans){
		I.op ^= 1;
		output.eb(I);
	}
	printf("%d\n",SZ(output));
	for(info &I:output){
		if(!I.op) printf("- ");
		else printf("+ ");
		printf("%d %d\n",I.u,I.v);
	}
	return 0;
}

源文件, 语言: C++20

詳細信息

Subtask #1:

score: 1

Accepted

Test #1:

score: 1

Accepted

time: 1ms

memory: 3892kb

input:

output:

result:

ok

Test #2:

score: 1

Accepted

time: 0ms

memory: 3892kb

input:

output:

result:

ok

Test #3:

score: 1

Accepted

time: 1ms

memory: 3904kb

input:

output:

result:

ok

Test #4:

score: 1

Accepted

time: 1ms

memory: 3904kb

input:

output:

2
- 2 3
+ 2 3

result:

ok

Test #5:

score: 1

Accepted

time: 1ms

memory: 3892kb

input:

output:

result:

ok

Test #6:

score: 1

Accepted

time: 1ms

memory: 3804kb

input:

output:

result:

ok

Test #7:

score: 1

Accepted

time: 0ms

memory: 3892kb

input:

output:

result:

ok

Test #8:

score: 1

Accepted

time: 0ms

memory: 3956kb

input:

output:

result:

ok

Test #9:

score: 1

Accepted

time: 1ms

memory: 3912kb

input:

output:

result:

ok

Subtask #2:

score: 1

Accepted

Test #10:

score: 1

Accepted

time: 1ms

memory: 3860kb

input:

output:

result:

ok

Test #11:

score: 1

Accepted

time: 1ms

memory: 3920kb

input:

output:

result:

ok

Test #12:

score: 1

Accepted

time: 1ms

memory: 3960kb

input:

output:

result:

ok

Test #13:

score: 1

Accepted

time: 1ms

memory: 3848kb

input:

output:

result:

ok

Test #14:

score: 1

Accepted

time: 1ms

memory: 3896kb

input:

output:

result:

ok

Test #15:

score: 1

Accepted

time: 1ms

memory: 3904kb

input:

output:

result:

ok

Test #16:

score: 1

Accepted

time: 1ms

memory: 3836kb

input:

output:

result:

ok

Test #17:

score: 1

Accepted

time: 0ms

memory: 3920kb

input:

output:

result:

ok

Test #18:

score: 1

Accepted

time: 0ms

memory: 3920kb

input:

output:

result:

ok

Test #19:

score: 1

Accepted

time: 1ms

memory: 3852kb

input:

output:

result:

ok

Test #20:

score: 1

Accepted

time: 1ms

memory: 3900kb

input:

output:

result:

ok

Test #21:

score: 1

Accepted

time: 1ms

memory: 3972kb

input:

output:

result:

ok

Test #22:

score: 1

Accepted

time: 1ms

memory: 3924kb

input:

output:

result:

ok

Test #23:

score: 1

Accepted

time: 0ms

memory: 3948kb

input:

output:

result:

ok

Test #24:

score: 1

Accepted

time: 1ms

memory: 3956kb

input:

output:

result:

ok

Test #25:

score: 1

Accepted

time: 1ms

memory: 3836kb

input:

output:

result:

ok

Test #26:

score: 1

Accepted

time: 0ms

memory: 3828kb

input:

output:

result:

ok

Test #27:

score: 1

Accepted

time: 0ms

memory: 3900kb

input:

output:

result:

ok

Test #28:

score: 1

Accepted

time: 1ms

memory: 3904kb

input:

output:

result:

ok

Test #29:

score: 1

Accepted

time: 1ms

memory: 3908kb

input:

output:

result:

ok

Subtask #3:

score: 1

Accepted

Test #30:

score: 1

Accepted

time: 1ms

memory: 3936kb

input:

output:

result:

ok

Test #31:

score: 1

Accepted

time: 1ms

memory: 3936kb

input:

output:

result:

ok

Test #32:

score: 1

Accepted

time: 1ms

memory: 3848kb

input:

output:

result:

ok

Test #33:

score: 1

Accepted

time: 1ms

memory: 3828kb

input:

output:

result:

ok

Test #34:

score: 1

Accepted

time: 1ms

memory: 3924kb

input:

output:

result:

ok

Test #35:

score: 1

Accepted

time: 1ms

memory: 3932kb

input:

output:

result:

ok

Test #36:

score: 1

Accepted

time: 1ms

memory: 3932kb

input:

output:

result:

ok

Test #37:

score: 1

Accepted

time: 1ms

memory: 3812kb

input:

output:

result:

ok

Test #38:

score: 1

Accepted

time: 1ms

memory: 3920kb

input:

output:

result:

ok

Test #39:

score: 1

Accepted

time: 1ms

memory: 3980kb

input:

output:

result:

ok

Test #40:

score: 1

Accepted

time: 1ms

memory: 3880kb

input:

output:

result:

ok

Test #41:

score: 1

Accepted

time: 0ms

memory: 3936kb

input:

output:

result:

ok

Test #42:

score: 1

Accepted

time: 1ms

memory: 3944kb

input:

output:

result:

ok

Test #43:

score: 1

Accepted

time: 1ms

memory: 3864kb

input:

output:

result:

ok

Test #44:

score: 1

Accepted

time: 1ms

memory: 3788kb

input:

output:

result:

ok

Test #45:

score: 1

Accepted

time: 0ms

memory: 3880kb

input:

output:

result:

ok

Test #46:

score: 1

Accepted

time: 1ms

memory: 3936kb

input:

output:

result:

ok

Test #47:

score: 1

Accepted

time: 1ms

memory: 3916kb

input:

output:

result:

ok

Test #48:

score: 1

Accepted

time: 1ms

memory: 3908kb

input:

output:

result:

ok

Test #49:

score: 1

Accepted

time: 1ms

memory: 3792kb

input:

output:

result:

ok

Test #50:

score: 1

Accepted

time: 1ms

memory: 3924kb

input:

output:

result:

ok

Subtask #4:

score: 1

Accepted

Test #51:

score: 1

Accepted

time: 0ms

memory: 3880kb

input:

output:

result:

ok

Test #52:

score: 1

Accepted

time: 1ms

memory: 3996kb

input:

output:

result:

ok

Test #53:

score: 1

Accepted

time: 1ms

memory: 3812kb

input:

output:

result:

ok

Test #54:

score: 1

Accepted

time: 1ms

memory: 3904kb

input:

output:

result:

ok

Test #55:

score: 1

Accepted

time: 0ms

memory: 3948kb

input:

output:

result:

ok

Test #56:

score: 1

Accepted

time: 1ms

memory: 4040kb

input:

output:

result:

ok

Test #57:

score: 1

Accepted

time: 1ms

memory: 3912kb

input:

output:

result:

ok

Test #58:

score: 1

Accepted

time: 1ms

memory: 4000kb

input:

output:

result:

ok

Test #59:

score: 1

Accepted

time: 1ms

memory: 3904kb

input:

output:

result:

ok

Test #60:

score: 1

Accepted

time: 1ms

memory: 3932kb

input:

output:

result:

ok

Test #61:

score: 1

Accepted

time: 0ms

memory: 4092kb

input:

output:

result:

ok

Test #62:

score: 1

Accepted

time: 1ms

memory: 3972kb

input:

output:

result:

ok

Test #63:

score: 1

Accepted

time: 1ms

memory: 3920kb

input:

output:

result:

ok

Test #64:

score: 1

Accepted

time: 1ms

memory: 3960kb

input:

output:

result:

ok

Test #65:

score: 1

Accepted

time: 1ms

memory: 4016kb

input:

output:

result:

ok

Test #66:

score: 1

Accepted

time: 1ms

memory: 3844kb

input:

output:

result:

ok

Test #67:

score: 1

Accepted

time: 1ms

memory: 3968kb

input:

output:

result:

ok

Test #68:

score: 1

Accepted

time: 1ms

memory: 3972kb

input:

output:

result:

ok

Test #69:

score: 1

Accepted

time: 1ms

memory: 3960kb

input:

output:

result:

ok

Test #70:

score: 1

Accepted

time: 1ms

memory: 4008kb

input:

output:

result:

ok

Subtask #5:

score: 1

Accepted

Test #71:

score: 1

Accepted

time: 1ms

memory: 4008kb

input:

output:

result:

ok

Test #72:

score: 1

Accepted

time: 2ms

memory: 4024kb

input:

output:

result:

ok

Test #73:

score: 1

Accepted

time: 0ms

memory: 3908kb

input:

output:

result:

ok

Test #74:

score: 1

Accepted

time: 1ms

memory: 4008kb

input:

output:

result:

ok

Test #75:

score: 1

Accepted

time: 1ms

memory: 3912kb

input:

output:

result:

ok

Test #76:

score: 1

Accepted

time: 2ms

memory: 4092kb

input:

output:

result:

ok

Test #77:

score: 1

Accepted

time: 2ms

memory: 4016kb

input:

output:

result:

ok

Test #78:

score: 1

Accepted

time: 2ms

memory: 4108kb

input:

output:

result:

ok

Test #79:

score: 1

Accepted

time: 1ms

memory: 4080kb

input:

output:

result:

ok

Test #80:

score: 1

Accepted

time: 1ms

memory: 3964kb

input:

output:

result:

ok

Test #81:

score: 1

Accepted

time: 2ms

memory: 4020kb

input:

output:

result:

ok

Test #82:

score: 1

Accepted

time: 2ms

memory: 4108kb

input:

output:

result:

ok

Test #83:

score: 1

Accepted

time: 2ms

memory: 4168kb

input:

output:

result:

ok

Test #84:

score: 1

Accepted

time: 1ms

memory: 3976kb

input:

output:

result:

ok

Test #85:

score: 1

Accepted

time: 0ms

memory: 4032kb

input:

output:

result:

ok

Test #86:

score: 1

Accepted

time: 1ms

memory: 4040kb

input:

output:

result:

ok

Test #87:

score: 1

Accepted

time: 1ms

memory: 4092kb

input:

output:

result:

ok

Test #88:

score: 1

Accepted

time: 1ms

memory: 4052kb

input:

output:

result:

ok

Test #89:

score: 1

Accepted

time: 0ms

memory: 4012kb

input:

output:

result:

ok

Test #90:

score: 1

Accepted

time: 1ms

memory: 4052kb

input:

output:

result:

ok

Test #91:

score: 1

Accepted

time: 1ms

memory: 4044kb

input:

output:

result:

ok

Subtask #6:

score: 1

Accepted

Test #92:

score: 1

Accepted

time: 2ms

memory: 4148kb

input:

output:

result:

ok

Test #93:

score: 1

Accepted

time: 2ms

memory: 4112kb

input:

output:

result:

ok

Test #94:

score: 1

Accepted

time: 1ms

memory: 4020kb

input:

output:

result:

ok

Test #95:

score: 1

Accepted

time: 1ms

memory: 4084kb

input:

output:

result:

ok

Test #96:

score: 1

Accepted

time: 1ms

memory: 4092kb

input:

output:

result:

ok

Test #97:

score: 1

Accepted

time: 2ms

memory: 4136kb

input:

output:

result:

ok

Test #98:

score: 1

Accepted

time: 2ms

memory: 4232kb

input:

output:

result:

ok

Test #99:

score: 1

Accepted

time: 2ms

memory: 4172kb

input:

output:

result:

ok

Test #100:

score: 1

Accepted

time: 2ms

memory: 4116kb

input:

output:

result:

ok

Test #101:

score: 1

Accepted

time: 2ms

memory: 4200kb

input:

output:

result:

ok

Test #102:

score: 1

Accepted

time: 2ms

memory: 4072kb

input:

output:

result:

ok

Test #103:

score: 1

Accepted

time: 2ms

memory: 4068kb

input:

output:

result:

ok

Test #104:

score: 1

Accepted

time: 2ms

memory: 4248kb

input:

output:

result:

ok

Test #105:

score: 1

Accepted

time: 1ms

memory: 4012kb

input:

output:

result:

ok

Test #106:

score: 1

Accepted

time: 0ms

memory: 4108kb

input:

output:

result:

ok

Test #107:

score: 1

Accepted

time: 2ms

memory: 4072kb

input:

output:

result:

ok

Test #108:

score: 1

Accepted

time: 2ms

memory: 4064kb

input:

output:

result:

ok

Test #109:

score: 1

Accepted

time: 2ms

memory: 4064kb

input:

output:

result:

ok

Test #110:

score: 1

Accepted

time: 1ms

memory: 4200kb

input:

output:

result:

ok

Test #111:

score: 1

Accepted

time: 1ms

memory: 4144kb

input:

output:

result:

ok

Subtask #7:

score: 1

Accepted

Test #112:

score: 1

Accepted

time: 6ms

memory: 4548kb

input:

output:

result:

ok

Test #113:

score: 1

Accepted

time: 3ms

memory: 4620kb

input:

output:

result:

ok

Test #114:

score: 1

Accepted

time: 0ms

memory: 4348kb

input:

output:

result:

ok

Test #115:

score: 1

Accepted

time: 4ms

memory: 4712kb

input:

output:

result:

ok

Test #116:

score: 1

Accepted

time: 4ms

memory: 4304kb

input:

output:

result:

ok

Test #117:

score: 1

Accepted

time: 7ms

memory: 4656kb

input:

output:

result:

ok

Test #118:

score: 1

Accepted

time: 7ms

memory: 4608kb

input:

output:

result:

ok

Test #119:

score: 1

Accepted

time: 7ms

memory: 4608kb

input:

4000
9772
502 681
454 595
887 2822
2370 451
3883 2989
2260 2956
577 3822
277 1578
2176 2775
1174 3346
388 816
1230 3022
2354 1515
3146 3762
159 1676
892 3820
1232 3832
394 1966
3269 3426
881 1325
2287 1248
3574 275
473 2358
2013 2779
3022 1677
173 266
1642 1791
1733 3928
2666 3821
2215 532
2041 1308...

output:

result:

ok

Test #120:

score: 1

Accepted

time: 6ms

memory: 4432kb

input:

output:

result:

ok

Test #121:

score: 1

Accepted

time: 3ms

memory: 4556kb

input:

4000
10000
272 1717
1638 610
698 1594
1722 2155
2561 710
1464 3197
1405 1178
3991 3366
2914 2096
3859 1076
1336 2320
342 2407
870 17
1534 1778
1130 3693
3357 1140
2030 1441
912 920
3003 1583
2240 377
5 1312
2983 2023
1543 203
2792 2577
1965 3406
197 1596
1501 2072
334 627
3268 887
2900 2711
3634 213...

output:

result:

ok

Test #122:

score: 1

Accepted

time: 7ms

memory: 4652kb

input:

output:

result:

ok

Test #123:

score: 1

Accepted

time: 8ms

memory: 4716kb

input:

output:

result:

ok

Test #124:

score: 1

Accepted

time: 7ms

memory: 4684kb

input:

output:

result:

ok

Test #125:

score: 1

Accepted

time: 4ms

memory: 4292kb

input:

output:

result:

ok

Test #126:

score: 1

Accepted

time: 5ms

memory: 4320kb

input:

4000
6780
3071 1320
2734 3687
2134 2092
1168 2685
3543 1134
875 2491
1924 694
2771 29
727 816
982 3491
1132 1762
3505 3687
1320 2807
1144 1721
2177 3687
2845 1961
2280 1404
316 599
1233 3193
36 2554
2493 3308
2020 3474
2571 3527
2356 427
1063 2612
3269 3262
3669 152
531 3
1828 2725
929 1303
2594 386...

output:

result:

ok

Test #127:

score: 1

Accepted

time: 6ms

memory: 4424kb

input:

output:

result:

ok

Test #128:

score: 1

Accepted

time: 0ms

memory: 4400kb

input:

output:

result:

ok

Test #129:

score: 1

Accepted

time: 7ms

memory: 4492kb

input:

4000
9594
2483 1469
1532 1515
3199 1902
2817 3220
410 1128
3134 1827
1113 3527
2505 2931
2184 1182
3924 3158
403 827
1981 3099
2029 2444
2584 194
1894 1464
1539 1966
133 108
1055 3975
2367 1843
2593 3281
2443 2955
52 2513
2311 1944
1586 1787
2879 1211
2119 3146
3105 1658
1636 1937
1568 3921
3258 105...

output:

result:

ok

Test #130:

score: 1

Accepted

time: 4ms

memory: 4736kb

input:

output:

result:

ok

Test #131:

score: 1

Accepted

time: 4ms

memory: 4728kb

input:

output:

result:

ok

Test #132:

score: 1

Accepted

time: 2ms

memory: 4252kb

input:

output:

result:

ok

Subtask #8:

score: 1

Accepted

Test #133:

score: 1

Accepted

time: 4ms

memory: 5220kb

input:

output:

result:

ok

Test #134:

score: 1

Accepted

time: 14ms

memory: 5444kb

input:

5988
20000
4830 3243
2756 3543
704 69
5615 1438
5446 4783
3171 142
5422 695
5782 3705
4214 4038
5163 2386
1504 1957
2560 4301
930 2556
5851 5173
115 4946
1964 5506
1390 5436
2653 5540
2262 2916
3784 3014
2075 4526
2919 4832
991 3953
3543 886
2764 5858
5365 2558
2321 5958
4900 705
2379 4385
4851 1622...

output:

result:

ok

Test #135:

score: 1

Accepted

time: 9ms

memory: 5248kb

input:

output:

result:

ok

Test #136:

score: 1

Accepted

time: 6ms

memory: 5844kb

input:

output:

result:

ok

Test #137:

score: 1

Accepted

time: 3ms

memory: 5164kb

input:

output:

result:

ok

Test #138:

score: 1

Accepted

time: 7ms

memory: 5780kb

input:

output:

result:

ok

Test #139:

score: 1

Accepted

time: 11ms

memory: 5688kb

input:

output:

result:

ok

Test #140:

score: 1

Accepted

time: 7ms

memory: 5772kb

input:

8530
17940
233 7174
2575 5795
3224 2983
6480 4953
4110 4257
5583 5878
1228 2539
693 1909
5893 897
1381 4030
2070 7276
5476 6141
3777 4511
809 4455
2735 3815
33 6191
1053 8191
8332 5535
69 4191
6629 8308
5926 3102
7630 7413
5584 8314
861 8391
8416 6467
7119 3025
7385 3897
7855 2898
7061 4110
6522 761...

output:

result:

ok

Test #141:

score: 1

Accepted

time: 11ms

memory: 5828kb

input:

output:

result:

ok

Test #142:

score: 1

Accepted

time: 15ms

memory: 5812kb

input:

output:

result:

ok

Test #143:

score: 1

Accepted

time: 15ms

memory: 5768kb

input:

output:

result:

ok

Test #144:

score: 1

Accepted

time: 11ms

memory: 6292kb

input:

output:

result:

ok

Test #145:

score: 1

Accepted

time: 12ms

memory: 6168kb

input:

output:

result:

ok

Test #146:

score: 1

Accepted

time: 10ms

memory: 5196kb

input:

output:

result:

ok

Test #147:

score: 1

Accepted

time: 12ms

memory: 5192kb

input:

output:

result:

ok

Test #148:

score: 1

Accepted

time: 10ms

memory: 5384kb

input:

output:

result:

ok

Test #149:

score: 1

Accepted

time: 8ms

memory: 5760kb

input:

output:

54935
+ 1 9425
+ 1 3118
+ 1 7597
+ 1 7300
+ 1 4582
+ 1 7763
+ 1 1865
+ 1 212
+ 1 9449
+ 1 5363
+ 1 2574
+ 1 6476
+ 1 7663
+ 1 774
+ 1 6150
+ 1 6541
+ 1 6926
+ 1 5119
+ 1 5549
+ 1 9827
+ 1 4171
+ 1 1471
+ 1 3776
+ 1 4148
+ 1 2633
+ 1 4816
+ 1 3085
+ 1 5646
+ 1 7397
+ 1 1155
+ 1 4734
+ 1 3116
+ 1 4852...

result:

ok

Test #150:

score: 1

Accepted

time: 14ms

memory: 5736kb

input:

output:

result:

ok

Test #151:

score: 1

Accepted

time: 4ms

memory: 6000kb

input:

10000
9999
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 6412
6412 9419
9419 6626
6626 3213
3213 109
109 2658
2658 2984
2984 1547
1547 7676
7676 8071
8071 4378
4378 7782
7782 7086
7086 9852
9852 1378
1378 2849
2849 8572
8572 9343
9343 5708
5708 1468
1468 2938
2938 8525
8525 9103
9103 561
561 4209
4209 636...

output:

result:

ok

Test #152:

score: 1

Accepted

time: 4ms

memory: 6008kb

input:

output:

result:

ok

Subtask #9:

score: 1

Accepted

Test #153:

score: 1

Accepted

time: 15ms

memory: 5860kb

input:

14707
17215
6756 405
12220 7729
5130 2987
4230 11416
14140 1338
13330 9266
4937 5289
13405 3659
574 4609
5204 3245
4975 2161
11210 3636
10189 10199
7401 9877
2008 6508
4419 4957
7160 9652
1891 6267
5461 1300
94 8088
6141 12560
7026 956
9897 7948
1545 14440
5422 3832
3778 4614
12647 6491
2070 6050
26...

output:

result:

ok

Test #154:

score: 1

Accepted

time: 20ms

memory: 7356kb

input:

output:

91964
+ 1 845
+ 1 497
+ 1 2120
+ 1 1215
+ 1 883
+ 1 547
+ 1 1261
+ 1 226
+ 1 1161
+ 1 1056
+ 1 1346
+ 1 1429
+ 1 1789
+ 1 480
+ 1 232
+ 1 1719
+ 1 2376
+ 1 1729
+ 1 1112
+ 1 3744
+ 1 7184
+ 1 7744
+ 1 1140
+ 1 3054
+ 1 730
+ 1 1418
+ 1 3366
+ 1 619
+ 1 1797
+ 1 1644
+ 1 671
+ 1 624
+ 1 6440
+ 1 4640...

result:

ok

Test #155:

score: 1

Accepted

time: 16ms

memory: 6656kb

input:

20000
19999
6779 6786
11361 11358
2740 18695
7151 10947
10335 13173
7600 1588
4554 1887
18818 9822
8343 19637
14365 1209
11306 9983
18364 8855
1934 3673
10801 15137
622 1493
14161 19202
19991 4361
4381 703
11361 13056
8397 3595
9062 769
502 8643
13543 10224
9392 19998
8842 5123
1563 11603
13616 1825...

output:

79986
+ 1 13353
+ 1 279
+ 1 4381
+ 1 703
+ 1 1730
+ 1 149
+ 1 668
+ 1 1541
+ 1 13182
+ 1 12385
+ 1 3290
+ 1 2343
+ 1 4515
+ 1 18139
+ 1 16092
+ 1 8294
+ 1 13623
+ 1 16125
+ 1 10586
+ 1 1308
+ 1 7609
+ 1 4248
+ 1 11717
+ 1 19928
+ 1 7990
+ 1 1746
+ 1 877
+ 1 10722
+ 1 11494
+ 1 4767
+ 1 2304
+ 1 2949...

result:

ok

Test #156:

score: 1

Accepted

time: 12ms

memory: 7840kb

input:

20000
19999
5663 15279
9706 7732
336 14439
17672 11908
17224 9260
17489 2068
3535 7535
10822 14935
16849 3571
18255 12276
18249 19079
18247 10370
17679 18406
8123 17212
5832 869
17946 1916
17929 1655
15579 12538
529 12641
14267 3876
2900 14814
17841 4131
3153 14491
17053 12201
938 14326
7290 12380
6...

output:

result:

ok

Test #157:

score: 1

Accepted

time: 16ms

memory: 7036kb

input:

20000
19999
12714 15754
9857 8966
10589 18787
19553 525
11746 1215
12585 6738
19304 18917
14048 13232
10560 10720
14578 18969
5883 2678
8561 4839
4439 7703
7046 277
18438 5986
13709 7072
13794 13425
4784 8321
9087 13164
14344 1959
5387 5029
8603 19455
16076 15839
19837 5366
2104 18864
19877 3313
742...

output:

result:

ok

Test #158:

score: 1

Accepted

time: 25ms

memory: 7968kb

input:

20000
35000
1192 5153
15850 9439
10309 14480
17829 8270
2237 15560
7735 11314
16520 13122
5765 12905
11949 7050
735 11361
19041 15534
5404 10252
15222 13653
15678 19052
12583 3168
17979 17474
510 17793
3403 13651
5558 11378
17373 12159
4160 15917
2426 7530
15421 9529
19000 14939
8228 7497
3169 9409
...

output:

result:

ok

Test #159:

score: 1

Accepted

time: 29ms

memory: 7836kb

input:

18370
35000
7120 17974
3838 11365
5768 10525
14033 8860
15354 6219
1110 15862
728 14224
1338 17788
9765 15516
2740 6232
8608 2064
17046 16807
18110 17520
15733 6442
9242 10924
5951 14286
181 4660
2550 10473
16840 16227
232 3245
8665 15369
1765 4907
382 11210
5322 17562
1558 5047
4317 13254
14381 145...

output:

result:

ok

Test #160:

score: 1

Accepted

time: 25ms

memory: 7632kb

input:

16158
28892
8490 7486
5289 12464
6646 3162
3213 380
11339 4570
9969 7752
4166 13430
4664 11025
6690 1012
6300 11757
3316 1211
8894 7859
4029 11609
6367 18
11852 4497
14279 11602
676 12222
11149 3772
14040 2060
10075 4070
13717 8933
8307 7558
12124 13142
13388 7376
14559 7086
13145 2569
3168 7762
539...

output:

result:

ok

Test #161:

score: 1

Accepted

time: 20ms

memory: 7940kb

input:

20000
34751
15792 15773
18498 16046
15606 13260
19567 7474
15939 17414
9533 11434
15173 6723
15200 559
1423 7986
2865 14183
17136 16533
15042 8857
1293 9883
17547 15550
13074 17713
3223 17205
11109 2581
6809 5496
18529 11814
8367 5417
4047 7749
18764 9896
19932 4016
5577 9241
12830 9350
8452 1004
15...

output:

result:

ok

Test #162:

score: 1

Accepted

time: 30ms

memory: 8000kb

input:

20000
35000
10049 11697
11031 19190
7377 5055
12249 12103
6941 6513
17176 9208
11636 16280
15678 3181
3933 9444
17127 740
19351 16349
13809 19620
2609 10434
4396 4187
5950 11937
19306 11022
11160 19239
17937 6247
7965 7990
19565 2383
18631 17018
4684 2142
4672 5469
14579 13135
584 12460
2525 1356
14...

output:

result:

ok

Test #163:

score: 1

Accepted

time: 29ms

memory: 7704kb

input:

19866
34933
10602 6123
14321 2745
4514 718
2469 10965
10762 49
16796 5161
12821 11528
7342 17402
18062 19799
11658 1030
13777 3048
2964 15790
8466 3638
1770 17485
1884 11631
6442 8764
16990 9433
18010 3824
12988 16609
7108 1527
15907 4915
11111 13647
5429 995
8448 6192
14238 5465
483 17112
14912 568...

output:

result:

ok

Test #164:

score: 1

Accepted

time: 27ms

memory: 8648kb

input:

20000
35000
18158 16739
9716 19205
1160 11561
10693 15843
10618 15434
741 4575
19033 5173
8000 10693
8399 5077
15434 8823
10886 15524
4584 3472
17016 1597
4466 19205
10992 7936
5173 4317
875 15222
19722 7122
6544 13713
12695 15999
18725 7055
4466 6826
3988 15629
14588 6908
6460 1103
8771 3117
10653 ...

output:

result:

ok

Test #165:

score: 1

Accepted

time: 22ms

memory: 8304kb

input:

19895
34677
18218 5042
6184 9250
368 4699
6389 13193
3302 1815
1594 3630
1737 15613
11141 3720
7862 18791
6427 16172
5299 9569
18282 1707
18421 13364
11773 19262
5758 6138
18492 15412
3643 19353
6184 11826
19395 13369
7654 15894
17096 10661
18191 15336
14117 13791
14296 9014
10041 13616
10483 3769
1...

output:

result:

ok

Test #166:

score: 1

Accepted

time: 17ms

memory: 6716kb

input:

20000
23319
16059 19600
7039 18345
7928 2278
1765 1401
9172 4535
11357 5504
18390 2806
6553 5835
8215 15928
17120 17463
1677 16059
12619 5456
18204 16059
13256 1524
4027 9253
13869 3540
5763 10606
18843 14602
15154 9332
7619 3123
6856 16731
11900 9734
11557 6622
17959 16059
12199 16059
7758 16059
29...

output:

result:

ok

Test #167:

score: 1

Accepted

time: 18ms

memory: 6820kb

input:

20000
29845
13418 13249
18574 17771
1235 7250
16540 18641
3165 6465
14880 12162
8603 14432
10607 3202
14257 13207
9602 9814
6465 18901
8470 16810
277 12331
3314 10353
11581 3948
10661 11889
19524 12744
14176 14024
19120 5072
11943 2742
16329 10991
15468 6465
9132 1028
14832 1344
3172 6465
18745 6465...

output:

result:

ok

Test #168:

score: 1

Accepted

time: 17ms

memory: 7560kb

input:

20000
31630
15359 10022
9048 8826
7415 9304
11166 15000
3930 15691
13863 14907
8849 6009
17545 11330
1708 19253
14474 16078
14458 9154
7666 1013
19552 11397
8265 8898
9120 15244
14040 1780
12437 13022
19696 17691
10594 15000
7065 6443
4916 911
4153 18346
16542 13008
12352 10720
12802 7333
323 13894
...

output:

result:

ok

Test #169:

score: 1

Accepted

time: 22ms

memory: 7748kb

input:

20000
31660
5103 3815
16454 12958
1062 757
1304 15062
9520 13160
18216 6458
1923 8661
13735 13291
291 5307
19516 5048
13898 4147
6187 17312
19899 17151
3223 17132
4630 17923
9925 7738
12668 10701
2928 5243
10942 3757
19200 15298
18834 5844
13372 5959
1065 4167
19917 11018
18642 4760
19379 15114
1780...

output:

result:

ok

Test #170:

score: 1

Accepted

time: 28ms

memory: 7620kb

input:

20000
33356
9389 18914
12940 4397
11377 18661
18923 7113
18372 653
17040 9611
12004 13965
5509 7733
14843 5841
13098 1055
7904 12803
16858 749
8660 1865
4005 18276
2976 12716
16881 8870
2570 15733
9368 18333
13649 10696
13084 19332
8034 17327
4058 4260
14100 10264
9893 7597
9292 380
17000 14208
1789...

output:

result:

ok

Test #171:

score: 1

Accepted

time: 11ms

memory: 8456kb

input:

20000
19999
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 5177
5177 13422
13422 15902
15902 9052
9052 4584
4584 19500
19500 4406
4406 3670
3670 5639
5639 3310
3310 17113
17113 5192
5192 1280
1280 10643
10643 9555
9555 10877
10877 10153
10153 19873
19873 7452
7452 18441
18441 17660
17660 8775
8775 9227
922...

output:

result:

ok

Test #172:

score: 1

Accepted

time: 19ms

memory: 8356kb

input:

20000
19999
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 12636
12636 18156
18156 2734
2734 554
554 12563
12563 15789
15789 10036
10036 14280
14280 3743
3743 15907
15907 7034
7034 2071
2071 6284
6284 14167
14167 19893
19893 12711
12711 14311
14311 2729
2729 9817
9817 10473
10473 11578
11578 5684
5684 3522...

output:

result:

ok

Test #173:

score: 1

Accepted

time: 15ms

memory: 6024kb

input:

output:

result:

ok

Subtask #10:

score: 1

Accepted

Test #174:

score: 1

Accepted

time: 11ms

memory: 7336kb

input:

22315
25704
5856 19157
8513 4234
638 5685
19718 9543
10907 170
978 13050
2747 1041
18713 15952
15146 13270
22171 6385
3306 1989
20586 3259
19291 9203
19084 15179
10066 8110
20002 10325
16192 7218
22313 17022
13691 2970
14973 1993
4453 17401
3 3211
6947 8986
19000 20815
20859 21056
7068 14262
1589 21...

output:

result:

ok

Test #175:

score: 1

Accepted

time: 45ms

memory: 11828kb

input:

29208
50000
21838 26966
1535 19609
21981 10969
15343 6518
13179 20290
25057 16406
9867 19028
1750 9606
28751 21557
20351 20917
23568 3549
1419 15869
21089 5288
10735 5497
5316 13500
6412 1146
15286 13545
20071 19964
14451 11648
10877 19354
27704 805
17091 29006
12264 23937
22085 21254
21153 13003
57...

output:

result:

ok

Test #176:

score: 1

Accepted

time: 25ms

memory: 7612kb

input:

30000
29999
12089 9529
28904 14717
5777 7451
16001 26778
25806 17702
24688 18959
7585 12129
17368 28372
6271 16464
13198 2515
5389 7207
12698 1192
13196 18102
20186 2320
29547 18796
17384 17222
6705 8733
26470 7400
3784 5773
15072 7597
26274 16797
1395 11305
15063 8185
26350 21309
18377 29913
22117 ...

output:

result:

ok

Test #177:

score: 1

Accepted

time: 19ms

memory: 9488kb

input:

30000
29999
6219 25723
14754 20362
5401 2010
23080 10040
28884 13868
14018 29530
7801 17690
29264 23505
19054 3350
29979 18132
22480 28557
8526 2194
24032 20721
4240 24882
19037 22392
7575 21964
24921 20693
19201 29798
4076 3880
18915 1993
9142 26223
3351 8668
21082 3299
5665 15198
28839 14325
28757...

output:

result:

ok

Test #178:

score: 1

Accepted

time: 27ms

memory: 7748kb

input:

30000
29999
29631 19478
22904 13702
29928 28505
29774 13811
25243 25818
26247 20358
5628 27865
28487 6736
23076 1798
11519 11974
27190 26084
25022 24723
10280 19278
9412 18868
6889 18393
14327 58
19548 20393
21405 13307
29014 14681
3327 26913
3313 25219
22240 19254
25137 23762
18868 27629
2083 8602
...

output:

result:

ok

Test #179:

score: 1

Accepted

time: 37ms

memory: 12264kb

input:

30000
50000
12910 14167
21556 2123
17017 5072
15391 13302
10467 23775
3937 12084
14051 1837
20224 16631
11278 28192
4651 23451
8083 6341
7130 14637
9730 19453
681 8476
28373 6165
18522 2529
12314 9141
2110 7229
5916 3898
24465 4920
12675 5173
23916 28006
15667 27146
9959 25045
12284 17924
25247 2146...

output:

result:

ok

Test #180:

score: 1

Accepted

time: 41ms

memory: 10648kb

input:

30000
48900
16981 18171
25334 26543
12211 13146
26720 15653
28434 24918
25869 2813
20272 28066
27111 3102
17454 431
4041 11765
21621 9653
8709 5378
20725 9584
19551 28337
92 6936
23623 3552
6855 2248
21498 811
121 24102
13000 3912
6047 29898
19882 16685
26507 29956
29593 2764
11566 28796
21298 9115
...

output:

result:

ok

Test #181:

score: 1

Accepted

time: 39ms

memory: 10664kb

input:

30000
50000
4045 856
1078 3334
13878 15514
12143 4534
7913 18909
20071 1447
26367 21164
7508 13868
22626 11611
1531 14042
6384 13953
9527 19694
3799 9155
9381 21519
13235 5610
10227 1600
5638 26514
23782 23904
26592 20037
15452 3962
4442 14100
7523 4342
3125 7581
12899 20511
17614 11066
25345 11778
...

output:

result:

ok

Test #182:

score: 1

Accepted

time: 40ms

memory: 10700kb

input:

29973
50000
25910 5398
3346 11675
21945 2752
12382 19648
7521 7873
15998 27483
28937 7817
10341 26491
25411 15532
9926 25297
22748 5899
9230 2765
1262 20882
4836 24491
9940 9358
20840 1447
26862 7552
12737 4100
23743 25231
14879 12294
20516 24093
13173 20276
6619 8311
12426 8915
15227 5715
273 16006...

output:

159930
+ 1 19834
+ 1 16816
+ 1 18755
+ 1 21490
+ 1 20290
+ 1 25959
+ 1 25
+ 1 7226
+ 1 8749
+ 1 6689
+ 1 8428
+ 1 25616
+ 1 4889
+ 1 7275
+ 1 5532
+ 1 11388
+ 1 26575
+ 1 9275
+ 1 27837
+ 1 7337
+ 1 7530
+ 1 24492
+ 1 10308
+ 1 16922
+ 1 10768
+ 1 16956
+ 1 18107
+ 1 24061
+ 1 3422
+ 1 6199
+ 1 9809...

result:

ok

Test #183:

score: 1

Accepted

time: 45ms

memory: 10536kb

input:

29757
49977
18046 27767
12281 9487
16666 2821
25265 20244
9665 12813
20562 2711
15975 15884
20848 6460
11097 16983
19120 2040
7753 272
22544 12821
29490 24869
23718 21804
9134 28552
7579 8809
20389 26116
12466 7411
17830 17395
21545 99
29747 27350
14622 4316
11629 15901
9405 21469
3393 7363
10498 13...

output:

result:

ok

Test #184:

score: 1

Accepted

time: 41ms

memory: 11748kb

input:

29885
50000
25807 799
27797 12571
14433 4247
21266 8992
28036 4774
7785 3321
8553 9350
1279 24210
3779 28153
27153 23247
23371 15105
2261 6428
11362 23668
1546 8130
21225 6246
8913 27156
6879 12595
7923 1761
17179 18559
27143 24494
6839 8962
19203 20791
800 21585
4983 3139
14907 275
14909 19038
906 ...

output:

result:

ok

Test #185:

score: 1

Accepted

time: 29ms

memory: 11516kb

input:

29866
50000
14664 14978
19933 186
5746 16830
25435 23726
21956 7557
8239 26043
10378 17570
7557 26617
23437 18676
7246 18107
4342 15861
28176 15818
3949 12482
26178 14026
7289 6268
13529 18043
24823 10923
27093 1328
13250 7157
21102 26344
22616 17605
26226 1563
12328 10923
132 371
1538 5476
563 1742...

output:

159722
+ 1 16828
+ 1 7231
+ 1 13394
+ 1 10151
+ 1 4711
+ 1 18778
+ 1 8017
+ 1 16979
+ 1 3111
+ 1 19560
+ 1 20940
+ 1 22263
+ 1 7360
+ 1 3185
+ 1 4413
+ 1 15908
+ 1 340
+ 1 9831
+ 1 19309
+ 1 4162
+ 1 4288
+ 1 22735
+ 1 1289
+ 1 2139
+ 1 15594
+ 1 16281
+ 1 9927
+ 1 28994
+ 1 20996
+ 1 2180
+ 1 16639...

result:

ok

Test #186:

score: 1

Accepted

time: 37ms

memory: 13164kb

input:

29984
50000
8463 11999
6650 24405
4841 15535
18258 14241
12699 18450
8255 3607
17532 20819
5265 9026
23716 15394
10204 11043
16700 18208
8743 6338
16610 5923
18160 18823
18620 13705
1626 28866
3052 9729
19152 17918
19282 15277
18069 29447
18946 3583
9172 1489
754 14815
11298 3935
3888 12870
12277 12...

output:

159472
+ 1 13862
+ 1 18465
+ 1 29848
+ 1 13045
+ 1 21421
+ 1 29984
+ 1 17239
+ 1 11651
+ 1 20558
+ 1 23671
+ 1 17986
+ 1 17348
+ 1 22378
+ 1 26581
+ 1 11599
+ 1 27159
+ 1 4439
+ 1 6450
+ 1 18917
+ 1 13809
+ 1 23125
+ 1 10124
+ 1 19187
+ 1 12950
+ 1 25374
+ 1 8647
+ 1 3672
+ 1 3612
+ 1 17792
+ 1 5915...

result:

ok

Test #187:

score: 1

Accepted

time: 28ms

memory: 7748kb

input:

30000
35079
12432 22938
29760 12432
6181 27548
830 1049
23645 12432
12432 9839
29412 20647
23558 3542
12432 6942
26137 17270
19369 3775
12702 24222
12432 3846
16186 26290
11550 16741
12432 20602
12432 29095
21890 3057
29785 9174
7551 7776
9703 12000
16749 9338
12432 28997
15628 22482
19042 21896
374...

output:

result:

ok

Test #188:

score: 1

Accepted

time: 33ms

memory: 9336kb

input:

30000
42792
29073 2622
13374 29073
22043 7318
20851 29073
29073 26661
21504 20894
17718 6509
12103 10731
24452 29073
10283 29504
8105 16082
13202 17953
29073 19659
39 16255
20747 21414
24495 23898
7027 16357
7283 2512
27296 12730
29073 9042
2940 29073
11136 22845
8275 12451
18947 14928
14953 23332
9...

output:

result:

ok

Test #189:

score: 1

Accepted

time: 32ms

memory: 11304kb

input:

30000
45010
13837 2753
23916 21131
87 17112
19218 11222
13831 13867
11675 1106
22602 11665
26144 16124
10713 25298
13837 19072
8248 7445
8191 18110
11524 20514
984 13370
12424 13837
24804 457
5631 13713
11109 17059
16836 24850
13837 6351
15697 13837
13257 820
13837 10465
16281 7565
6391 7578
4704 25...

output:

result:

ok

Test #190:

score: 1

Accepted

time: 32ms

memory: 10120kb

input:

30000
45020
972 10721
18054 7576
19115 11437
29811 1663
22608 25434
20436 13500
23361 9218
4043 28695
21855 23352
19152 22516
17475 26974
27846 17514
17425 8391
18261 9628
24522 6351
14308 27707
19235 11075
14277 10544
273 4722
18583 12564
16741 9911
17920 11544
2387 12309
13222 14197
7956 12950
201...

output:

149978
+ 1 8590
+ 1 13671
+ 1 7612
+ 1 10242
+ 1 1229
+ 1 4415
+ 1 5834
+ 1 24821
+ 1 26641
+ 1 575
+ 1 9840
+ 1 14099
+ 1 531
+ 1 17597
+ 1 22959
+ 1 22357
+ 1 3536
+ 1 11312
+ 1 22942
+ 1 14276
+ 1 5457
+ 1 28760
+ 1 10192
+ 1 11384
+ 1 14353
+ 1 18712
+ 1 1575
+ 1 6264
+ 1 18588
+ 1 5079
+ 1 1469...

result:

ok

Test #191:

score: 1

Accepted

time: 31ms

memory: 10368kb

input:

30000
48342
15303 17987
256 26275
12364 24570
18234 139
17853 19197
19137 27545
8782 4638
20488 5611
1596 5724
26467 17142
28248 2500
15777 25450
6497 415
18766 1889
5108 20449
24167 22044
27526 11193
2941 4596
19143 23368
5039 26554
22742 16139
29128 29175
24603 12891
4889 11611
21 7612
20712 21093...

output:

result:

ok

Test #192:

score: 1

Accepted

time: 28ms

memory: 9944kb

input:

30000
29999
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11174
11174 22666
22666 25608
25608 15271
15271 13930
13930 8022
8022 3989
3989 9466
9466 7531
7531 11153
11153 12039
12039 10275
10275 26760
26760 22359
22359 27990
27990 10597
10597 7532
7532 1364
1364 3071
3071 14724
14724 13467
13467 27172
2717...

output:

result:

ok

Test #193:

score: 1

Accepted

time: 28ms

memory: 9848kb

input:

30000
29999
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 23722
23722 20205
20205 29499
29499 24741
24741 18277
18277 10701
10701 23468
23468 15330
15330 1328
1328 3446
3446 1114
1114 14321
14321 27375
27375 17175
17175 2958
2958 21856
21856 16104
16104 5438
5438 4177
4177 7206
7206 27914
27914 21823
2182...

output:

result:

ok

Extra Test:

score: 0

Extra Test Passed