QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#115604#6629. Travelling Traderyyyyxh#16 203ms65760kbC++174.2kb2023-06-26 12:51:232024-05-31 14:18:44

Judging History

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

  • [2024-05-31 14:18:44]
  • 评测
  • 测评结果:16
  • 用时:203ms
  • 内存:65760kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-26 12:51:23]
  • 提交

answer

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int N=200003;
int hd[N],ver[N<<1],nxt[N<<1],tot;
void add(int u,int v){
	nxt[++tot]=hd[u];hd[u]=tot;ver[tot]=v;
}
int w[N];
typedef long long ll;
namespace sub1{
	ll f[N];
	int x;
	int p[N];
	void dfs(int u,int fa){
		for(int i=hd[u];i;i=nxt[i]){
			int v=ver[i];
			if(v==fa) continue;
			dfs(v,u);
			if(f[v]>f[p[u]]) p[u]=v;
		}
		f[u]=f[p[u]]+w[u];
	}
	int stk[N],tp;
	void solve(){
		dfs(1,0);
		printf("%lld\n",f[1]);
		for(int i=1;i;i=p[i]) stk[++tp]=i;
		printf("%d\n",tp);
		for(int i=1;i<=tp;++i) printf("%d ",stk[i]);
		putchar('\n');
	}
}
namespace sub2{
	ll f[N][2],g[N];
	int q[N][2][4];
	int p[N];
	typedef pair<ll,int> pli;
	set<pli> st;
	void chmx(int u,int t,ll val,int *cq){
		if(f[u][t]<val){
			f[u][t]=val;
			for(int c=0;c<4;++c) q[u][t][c]=cq[c];
		}
	}
	void dfs(int u,int fa){
		ll sum=w[u];
		for(int i=hd[u];i;i=nxt[i]){
			int v=ver[i];
			if(v==fa) continue;
			dfs(v,u);
			sum+=w[v];
		}
		st.clear();
		g[u]=sum;
		for(int i=hd[u];i;i=nxt[i]){
			int v=ver[i];
			if(v==fa) continue;
			if(g[v]-w[v]>g[p[u]]-w[p[u]]) p[u]=v;
			st.emplace(g[v]-w[v],v);
		}
		g[u]+=g[p[u]]-w[p[u]];
		f[u][0]=f[u][1]=sum;
		for(int i=hd[u];i;i=nxt[i]){
			int v=ver[i];
			if(v==fa) continue;
			st.erase(pli(g[v]-w[v],v));
			ll cur=w[u];
			int cq[4]={v,0,0,0};
			
			chmx(u,0,cur+f[v][0],cq);
			cq[1]=1;cur=sum;
			chmx(u,0,cur+f[v][0]-w[v],cq);
			if(!st.empty()){
				auto [d1,v1]=*prev(st.end());
				st.erase(prev(st.end()));
				cur+=d1;cq[2]=v1;
				chmx(u,0,cur+f[v][0]-w[v],cq);
				if(!st.empty()){
					auto [d2,v2]=*prev(st.end());
					cur+=d2;cq[3]=v2;
					chmx(u,0,cur+f[v][1]-w[v],cq);
					cur-=d2;cq[3]=0;
				}
				cur-=d1;cq[2]=0;
				st.emplace(d1,v1);
			}
			cq[1]=0;cur=w[u];
			
			chmx(u,1,cur+f[v][0],cq);
			cq[1]=1;cur=sum;
			chmx(u,1,cur+f[v][1]-w[v],cq);
			if(!st.empty()){
				auto [d1,v1]=*prev(st.end());
				cur+=d1;cq[2]=v1;
				chmx(u,1,cur+f[v][1]-w[v],cq);
				cur-=d1;cq[2]=0;
			}
			cq[1]=0;cur=w[u];
			
			st.emplace(g[v]-w[v],v);
		}
	}
	int seq[N],rk;
	void t1(int,int);
	void t2(int,int);
	void t1(int u,int fa){
		seq[++rk]=u;
		if(p[u]) t2(p[u],u);
		for(int i=hd[u];i;i=nxt[i]){
			int v=ver[i];
			if(v==fa||v==p[u]) continue;
			seq[++rk]=v;
		}
	}
	void t2(int u,int fa){
		for(int i=hd[u];i;i=nxt[i]){
			int v=ver[i];
			if(v==fa||v==p[u]) continue;
			seq[++rk]=v;
		}
		if(p[u]) t1(p[u],u);
		seq[++rk]=u;
	}
	void cons(int u,int t,int fa){
		if(f[u][t]<=g[u]) return t1(u,fa);
		int nx=q[u][t][0];
		if(t){
			seq[++rk]=u;
			if(q[u][t][1]){
				if(q[u][t][2]) t2(q[u][t][2],u);
				for(int i=hd[u];i;i=nxt[i]){
					int v=ver[i];
					if(v==fa||v==nx||v==q[u][t][2]) continue;
					seq[++rk]=v;
				}
				cons(nx,1,u);
			}
			else cons(nx,0,u);
		}
		else{
			if(q[u][t][1]){
				if(q[u][t][2]){
					if(q[u][t][3]){
						for(int i=hd[u];i;i=nxt[i]){
							int v=ver[i];
							if(v==q[u][t][2]||v==q[u][t][3]||v==nx||v==fa) continue;
							seq[++rk]=v;
						}
						t1(q[u][t][2],u);
						seq[++rk]=u;
						t2(q[u][t][3],u);
						cons(nx,1,u);
					}
					else{
						for(int i=hd[u];i;i=nxt[i]){
							int v=ver[i];
							if(v==q[u][t][2]||v==nx||v==fa) continue;
							seq[++rk]=v;
						}
						t1(q[u][t][2],u);
						seq[++rk]=u;
						cons(nx,0,u);
					}
				}
				else{
					for(int i=hd[u];i;i=nxt[i]){
						int v=ver[i];
						if(v==fa||v==nx) continue;
						seq[++rk]=v;
					}
					seq[++rk]=u;
					cons(nx,0,u);
				}
			}
			else{
				seq[++rk]=u;
				cons(nx,0,u);
			}
		}
	}
	void solve(){
		dfs(1,0);
		printf("%lld\n",f[1][1]);
		cons(1,1,0);
		printf("%d\n",rk);
		for(int i=1;i<=rk;++i) printf("%d ",seq[i]); 
		putchar('\n');
	}
}
int n,k;
int main(){
	n=read();k=read();
	for(int i=1;i<n;++i){
		int u=read(),v=read();
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;++i) w[i]=read();
	if(k==1) sub1::solve();
	if(k==2) sub2::solve();
	return 0;
}

详细

Subtask #1:

score: 2
Accepted

Test #1:

score: 2
Accepted
time: 1ms
memory: 3812kb

input:

2 1
1 2
255959470 961356354

output:

1217315824
2
1 2 

result:

ok correct!

Test #2:

score: 2
Accepted
time: 1ms
memory: 5960kb

input:

1000 1
730 89
762 280
923 523
740 22
679 350
448 769
102 712
154 965
219 32
238 289
484 502
183 311
999 682
806 450
275 101
131 197
749 720
131 937
960 202
503 320
95 262
595 133
809 560
659 451
843 218
258 842
564 316
729 727
413 237
606 531
469 258
612 8
707 539
359 680
957 639
381 708
104 490
234...

output:

95535
17
1 173 449 472 396 545 668 270 981 489 852 836 763 6 218 843 758 

result:

ok correct!

Test #3:

score: 2
Accepted
time: 15ms
memory: 12956kb

input:

200000 1
111811 133538
179217 151840
171974 117009
187613 169656
64662 13136
132434 89348
52802 175565
194821 191312
196047 99457
40339 152969
29669 180026
147677 57771
119598 58048
80707 146623
72232 101624
48109 11800
71536 69
31573 129
24409 17263
1033 148614
66977 149926
138624 87653
141889 1178...

output:

221
35
1 145832 90178 52464 3517 55709 39776 67451 59386 143855 102872 38865 13093 177086 7366 190908 160039 69864 196809 13257 612 171083 182883 14221 93359 52156 27994 103745 151704 138607 5346 14735 29598 89600 128747 

result:

ok correct!

Test #4:

score: 2
Accepted
time: 22ms
memory: 10956kb

input:

200000 1
102636 78442
179388 84484
161437 35179
102313 154299
62439 71542
176361 125315
174129 186376
180886 54947
154823 114239
174647 112385
136495 187134
157035 96260
101101 192444
58209 23947
55494 191600
168007 162648
140149 73180
130665 180633
129328 67380
90262 134914
185905 104220
111321 154...

output:

21795891322
36
1 13557 199188 104317 71891 69787 1221 63258 191536 179446 83510 187880 124824 43888 83237 194602 59080 196038 195977 18490 43421 110298 60011 137785 140692 48345 68279 128780 198550 29394 56331 112092 192199 177180 16418 142142 

result:

ok correct!

Test #5:

score: 2
Accepted
time: 27ms
memory: 10836kb

input:

200000 1
682 75953
92444 160568
113369 93705
154622 193304
149619 128186
104784 48913
131684 161196
25886 151867
89191 19511
99233 137377
104650 120096
64347 93526
111350 71598
7568 120116
123497 76821
25436 190715
99884 33654
109438 69462
165464 2475
163215 34551
33926 85078
101208 193355
50705 828...

output:

99327575017
197
1 178606 82034 53029 10508 21404 203 109187 121716 142023 3901 36728 9916 192913 18250 170199 113960 179753 163922 179588 31797 31645 183321 83207 13973 128176 38001 160968 9055 62809 168173 43933 187373 123795 114656 2192 193151 25062 141855 133596 155793 64049 57320 93903 33957 139...

result:

ok correct!

Test #6:

score: 2
Accepted
time: 25ms
memory: 10960kb

input:

200000 1
91999 92900
195726 58991
132067 99937
168188 152017
188495 19779
105961 45241
53406 75757
85118 170259
46250 47585
132248 8609
195110 32777
164307 95643
133411 739
170952 145623
19297 14414
171045 97619
74663 193421
139543 189434
36319 56453
77520 91164
91469 30021
128798 62259
183807 15271...

output:

9098893435
13
1 164355 56677 150505 174723 115829 88068 105453 199874 190131 165416 182628 114943 

result:

ok correct!

Test #7:

score: 2
Accepted
time: 15ms
memory: 12168kb

input:

200000 1
189797 1
1 148138
1 95067
141831 1
168151 1
1 25692
95612 1
1 135979
1 141581
119622 1
1 131946
86508 1
98799 1
1 189104
1 117526
46338 1
1 166375
1 28026
165221 1
54204 1
1 98743
1 181414
1 34313
1 71302
1 161200
1 146339
1 47014
1 137258
1 57857
1 196493
1 99105
54487 1
104725 1
1 45203
1...

output:

1175349557
2
1 153544 

result:

ok correct!

Test #8:

score: 2
Accepted
time: 15ms
memory: 10908kb

input:

199999 1
56367 178046
1 156890
170478 1
111308 177326
1 188427
1 90169
126610 1
161930 167698
96500 126424
118330 158517
186608 1
95505 107863
1 142887
72279 27494
1 114700
118535 1
68584 63156
97555 19966
39239 1
128030 1
1 86200
66974 1
34616 47100
173578 1
1 117279
89769 43412
1 89670
103573 1
13...

output:

2999144210
3
1 52552 129910 

result:

ok correct!

Test #9:

score: 2
Accepted
time: 46ms
memory: 24196kb

input:

200000 1
95601 67789
174512 65854
198542 123861
153390 92355
141969 168754
177054 101194
25665 15524
131869 168080
171051 30732
97293 119758
103002 59019
141990 124310
161550 116618
2585 170410
132999 38200
99202 98733
73949 155033
144918 64086
1594 34916
37138 165382
13452 170885
136973 62178
15250...

output:

200000000000000
200000
1 47213 179780 132180 145558 41335 179095 156350 24912 104386 94658 54370 97034 108043 73905 141018 157563 199841 176455 147422 87545 190562 135095 24903 62484 36389 156106 45144 120321 4911 173474 102976 13602 68252 7332 141515 59337 182112 124040 38089 15458 161370 41901 144...

result:

ok correct!

Test #10:

score: 2
Accepted
time: 32ms
memory: 17452kb

input:

200000 1
122636 169264
76896 89915
72116 125306
186356 74852
84394 177419
21725 144848
106395 111991
189102 195804
6151 170169
185460 146764
6304 149801
147880 99539
6202 175326
104277 26515
39402 33436
116555 185545
44341 92305
197925 125286
28215 102176
182103 160554
105237 169007
105618 75618
190...

output:

49951940813408
100001
1 88700 18534 14218 21693 84470 150823 121376 192964 139616 11067 93019 188349 55336 13628 87630 31553 28945 29827 140175 179655 10038 38915 99968 89953 72978 102045 45280 176852 171879 100086 93399 183932 84482 111738 112608 136016 101850 19371 96135 54333 95939 2865 140685 13...

result:

ok correct!

Test #11:

score: 2
Accepted
time: 12ms
memory: 12556kb

input:

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

output:

13954593167
18
1 2 5 10 20 40 80 161 323 647 1295 2590 5181 10363 20727 41454 82908 165817 

result:

ok correct!

Subtask #2:

score: 7
Accepted

Test #12:

score: 7
Accepted
time: 0ms
memory: 12088kb

input:

2 2
2 1
243296356 635616793

output:

878913149
2
1 2 

result:

ok correct!

Test #13:

score: 7
Accepted
time: 0ms
memory: 12000kb

input:

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

output:

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

result:

ok correct!

Test #14:

score: 7
Accepted
time: 0ms
memory: 10016kb

input:

200 2
150 170
21 33
96 152
143 26
136 70
92 159
34 164
163 182
74 115
93 61
151 83
81 119
10 146
114 170
39 83
139 4
173 41
193 96
87 57
14 164
107 51
45 15
157 17
43 183
96 30
11 137
55 18
138 81
87 12
112 122
159 82
195 185
75 71
16 191
33 88
70 195
149 114
106 160
96 118
92 44
9 141
107 143
151 2...

output:

57921623677
100
1 135 89 194 179 151 39 83 27 40 112 125 180 120 117 122 72 99 33 131 105 96 114 171 28 110 149 59 170 193 138 94 162 88 21 45 129 25 78 62 127 36 199 15 12 76 70 53 159 17 178 24 44 41 67 173 116 42 186 92 32 5 101 197 82 121 198 29 87 64 93 19 126 8 141 37 100 3 9 52 108 61 54 137 ...

result:

ok correct!

Test #15:

score: 7
Accepted
time: 0ms
memory: 12088kb

input:

200 2
33 5
171 115
70 64
38 42
123 154
167 183
152 177
36 102
98 116
125 187
61 148
143 136
62 169
102 142
86 189
115 100
85 172
136 50
158 113
133 5
10 108
90 178
90 21
127 28
122 189
115 18
83 109
197 11
53 70
191 141
166 90
70 9
74 148
160 7
186 151
197 86
147 82
107 161
122 140
110 58
179 25
107...

output:

47106979559
87
1 111 51 7 130 67 160 52 20 138 126 127 48 62 189 70 65 156 9 76 155 196 36 80 53 64 110 175 193 135 177 78 24 5 133 33 149 152 58 13 119 117 106 184 191 73 88 154 139 174 59 170 27 4 123 141 120 145 167 34 15 146 50 143 136 183 39 108 118 10 129 37 115 95 66 100 165 71 171 18 40 47 1...

result:

ok correct!

Test #16:

score: 7
Accepted
time: 2ms
memory: 10016kb

input:

200 2
139 197
14 69
160 138
115 60
1 141
176 33
94 88
108 26
106 20
96 60
126 180
171 110
140 91
138 63
57 183
42 62
126 163
126 64
87 167
22 142
190 112
27 120
187 109
83 111
23 196
95 47
105 177
96 170
192 113
136 188
24 198
116 137
53 177
178 38
30 158
125 64
123 132
36 114
77 192
125 165
194 7
9...

output:

73032451334
133
1 141 50 7 75 194 65 124 53 105 177 139 122 134 46 16 14 197 114 99 83 193 22 67 120 70 51 175 32 107 101 36 15 90 43 189 146 91 191 144 95 172 73 45 174 167 87 159 109 81 4 25 140 199 2 198 82 170 60 42 121 157 78 184 155 182 54 186 62 96 158 24 165 3 136 17 10 127 143 39 188 149 12...

result:

ok correct!

Test #17:

score: 7
Accepted
time: 2ms
memory: 12088kb

input:

200 2
182 43
15 179
37 173
45 38
62 4
131 151
83 188
84 58
183 148
155 59
141 133
128 19
191 170
129 87
67 156
120 199
94 11
162 27
175 86
73 50
143 94
81 103
84 120
12 19
59 38
48 34
127 41
196 87
135 69
43 119
54 176
180 112
89 60
67 117
149 18
53 61
12 1
46 67
25 38
8 52
119 51
162 197
12 31
166 ...

output:

63859058076
111
1 31 12 30 158 19 189 180 29 36 66 85 112 124 128 151 69 18 3 25 45 59 179 15 5 7 33 65 171 155 38 187 4 181 22 144 140 91 192 54 111 165 136 184 26 191 120 58 70 84 118 170 56 122 90 196 182 119 63 167 64 160 88 80 51 43 60 123 76 8 93 87 83 20 57 47 94 44 163 132 95 143 11 127 129 ...

result:

ok correct!

Test #18:

score: 7
Accepted
time: 2ms
memory: 10004kb

input:

200 2
12 76
61 106
151 109
163 180
11 135
109 179
35 199
86 104
82 109
80 70
15 123
180 154
134 91
187 81
167 4
27 71
174 101
124 127
154 29
173 175
172 61
59 109
53 55
76 55
174 67
50 169
180 32
1 182
126 3
148 146
58 127
26 181
189 47
10 156
120 112
157 149
136 166
146 122
59 17
99 136
55 138
49 1...

output:

59693686065
120
1 116 186 108 104 86 183 87 102 58 47 146 177 148 122 60 190 189 46 57 5 79 2 32 163 154 119 29 180 98 178 14 176 192 101 120 107 114 169 97 25 50 196 88 44 112 48 197 24 158 138 76 53 159 41 55 128 143 156 59 74 164 89 65 9 28 139 135 155 51 142 167 18 90 100 38 16 4 42 36 199 11 92...

result:

ok correct!

Test #19:

score: 7
Accepted
time: 0ms
memory: 12008kb

input:

200 2
33 83
16 197
177 12
71 47
85 60
34 49
96 78
30 39
63 122
95 17
168 74
89 83
62 134
45 166
48 6
178 91
151 72
153 47
104 174
86 140
33 134
24 51
129 71
48 94
141 93
64 118
155 50
43 28
182 92
31 142
105 56
156 100
83 69
179 90
140 127
186 148
16 47
175 4
123 173
27 50
154 186
107 98
200 20
66 6...

output:

61122293114
124
1 173 190 50 55 155 152 27 101 123 48 172 111 47 197 126 163 58 125 102 16 59 153 71 180 149 165 94 195 11 6 63 88 53 41 124 65 135 22 96 187 37 26 68 181 122 174 112 103 87 116 43 21 60 98 90 177 42 13 44 72 185 151 12 31 75 107 113 85 52 28 106 15 104 76 83 134 146 38 137 200 136 1...

result:

ok correct!

Test #20:

score: 7
Accepted
time: 0ms
memory: 10096kb

input:

200 2
91 28
137 24
181 33
82 19
90 182
180 77
2 6
190 176
100 181
13 140
52 77
85 189
28 29
176 22
7 180
55 176
99 113
6 93
28 51
117 44
180 127
114 174
102 92
13 14
129 181
80 24
95 28
181 195
162 4
28 188
55 162
59 131
47 45
145 176
136 197
145 57
159 117
143 106
192 106
126 28
43 23
51 73
109 28
...

output:

48771917800
98
1 79 64 109 188 95 51 29 91 126 166 21 135 113 26 99 46 103 104 40 130 36 28 198 172 63 13 62 133 11 117 12 97 145 55 22 190 93 30 17 65 84 81 102 59 37 131 92 8 136 151 24 6 176 158 69 155 160 90 82 106 50 125 165 49 192 143 19 129 48 23 43 71 78 41 67 132 199 96 25 181 180 156 76 14...

result:

ok correct!

Test #21:

score: 7
Accepted
time: 1ms
memory: 7992kb

input:

200 2
117 30
120 159
129 100
29 57
57 71
96 72
53 153
171 96
138 197
13 72
142 74
64 85
148 150
145 106
190 23
198 177
58 127
163 67
32 183
26 155
94 159
170 70
12 181
13 24
157 116
163 40
126 76
195 193
92 9
4 113
196 135
196 154
110 56
79 196
50 14
68 46
143 36
131 50
46 2
179 160
92 31
61 3
169 9...

output:

70064073402
147
1 197 165 18 6 98 168 180 136 122 47 167 121 103 48 138 123 104 163 73 162 81 67 161 21 174 189 119 145 170 16 193 93 175 8 141 76 63 34 159 105 44 143 172 65 36 82 94 200 126 137 155 195 70 75 106 85 91 43 190 133 148 97 41 125 56 110 111 150 140 160 23 64 37 144 128 100 7 182 157 1...

result:

ok correct!

Test #22:

score: 7
Accepted
time: 2ms
memory: 11992kb

input:

200 2
29 106
175 25
175 87
144 67
51 68
118 71
184 165
74 86
127 64
12 68
180 186
53 164
193 64
144 98
106 122
44 144
178 144
144 94
17 64
106 89
199 1
64 108
28 61
39 199
106 28
23 148
69 106
66 74
164 68
92 185
144 68
78 143
168 126
148 196
72 9
74 160
106 128
63 148
121 178
157 68
72 148
104 144
...

output:

64091222931
110
1 84 80 39 199 8 64 167 182 115 97 175 103 50 47 16 74 18 111 165 92 134 169 26 143 81 151 96 37 140 31 104 94 178 44 98 67 106 48 188 65 200 20 172 71 118 36 158 40 101 190 75 129 3 146 128 69 28 89 122 29 144 141 54 123 112 177 42 82 137 83 145 157 12 51 164 5 53 68 148 19 130 155 ...

result:

ok correct!

Test #23:

score: 7
Accepted
time: 2ms
memory: 9968kb

input:

200 2
161 12
189 84
46 61
69 75
139 170
146 21
162 91
20 125
40 78
152 25
81 140
15 138
39 184
85 183
29 59
166 126
127 24
125 56
94 26
92 37
33 196
168 16
75 64
148 57
112 142
185 46
49 195
76 18
88 79
70 125
194 136
12 154
77 195
10 2
86 155
90 170
83 67
38 179
172 175
198 191
11 51
67 42
25 93
18...

output:

82840243479
163
1 151 57 165 147 148 60 17 97 110 198 121 191 71 143 101 61 185 31 173 116 192 131 33 100 46 134 152 25 52 5 93 99 114 98 43 197 81 144 64 69 12 55 68 199 174 164 133 66 35 180 72 154 161 75 39 8 140 188 14 117 13 19 132 177 85 183 169 80 200 21 189 9 182 7 88 79 74 84 146 145 37 92 ...

result:

ok correct!

Test #24:

score: 7
Accepted
time: 0ms
memory: 12068kb

input:

200 2
19 106
54 55
83 185
106 178
78 194
51 66
133 200
106 58
106 35
163 150
50 104
96 105
124 105
41 66
124 22
54 106
27 93
106 133
196 124
58 83
106 193
124 110
194 165
150 124
194 13
42 149
127 154
121 159
106 26
100 181
124 82
1 80
177 45
69 100
54 189
61 19
70 106
134 175
168 134
6 112
44 100
1...

output:

60321563038
110
1 154 31 45 46 6 114 191 188 84 56 174 180 195 113 98 128 167 12 182 93 138 40 155 70 26 193 133 54 35 58 178 19 100 161 81 140 36 68 141 121 159 38 87 101 104 158 8 143 152 198 173 190 88 148 145 44 69 181 106 10 29 71 116 90 142 111 57 13 165 78 156 194 124 109 117 136 199 153 144 ...

result:

ok correct!

Test #25:

score: 7
Accepted
time: 2ms
memory: 9972kb

input:

200 2
104 32
163 164
138 166
140 114
144 134
193 184
94 25
196 140
119 160
29 34
170 7
175 60
122 185
85 133
9 53
95 89
171 158
34 155
67 32
73 125
167 128
27 48
157 119
105 2
13 142
134 120
71 118
66 117
182 59
156 43
84 91
126 80
55 192
34 68
64 194
131 75
81 151
117 102
145 104
99 4
3 65
91 35
79...

output:

80439812057
153
1 136 65 3 44 109 45 118 99 79 69 4 71 167 41 88 128 165 64 194 125 133 49 197 164 62 176 108 156 58 43 163 73 93 14 178 94 25 123 182 59 115 19 144 89 120 122 126 168 60 46 7 131 100 184 162 158 171 38 26 75 121 170 172 175 51 188 80 103 185 134 189 140 127 57 154 169 8 15 137 147 1...

result:

ok correct!

Test #26:

score: 7
Accepted
time: 2ms
memory: 12008kb

input:

200 2
105 64
190 149
84 15
184 93
52 80
182 129
160 51
108 184
105 167
9 77
61 80
109 84
161 188
121 2
121 20
175 60
80 154
105 88
25 60
88 10
41 123
105 135
99 184
100 98
152 105
1 75
184 199
163 102
63 88
56 184
83 13
101 123
107 50
120 42
8 78
105 45
105 121
184 92
105 129
136 124
123 139
88 19
7...

output:

51611310581
104
1 33 5 75 60 51 159 136 189 127 130 50 141 165 172 161 86 84 198 106 102 147 27 46 57 129 121 45 152 135 88 167 64 80 12 200 176 190 32 97 174 74 8 26 162 17 104 4 128 16 111 31 85 30 67 114 98 154 61 52 105 181 166 68 177 143 193 185 113 77 155 90 96 139 101 41 144 14 72 123 184 40 ...

result:

ok correct!

Test #27:

score: 7
Accepted
time: 0ms
memory: 9964kb

input:

200 2
8 1
1 22
39 1
168 1
136 1
197 1
1 142
1 4
18 1
187 1
1 74
156 1
1 94
118 1
1 86
1 76
30 1
52 1
1 42
144 1
105 1
64 1
1 9
137 1
112 1
101 1
75 1
1 113
1 164
1 29
1 60
1 167
1 135
1 192
196 1
48 1
1 179
170 1
158 1
1 145
47 1
1 98
143 1
184 1
84 1
72 1
20 1
109 1
1 106
1 3
1 79
55 1
1 77
102 1
1...

output:

89576768884
200
1 27 129 53 66 131 95 182 10 19 34 99 171 191 89 169 178 83 45 88 65 92 150 33 124 134 51 50 44 183 21 35 91 157 190 87 57 97 188 14 155 200 32 16 67 185 172 140 78 58 62 193 165 139 110 100 152 104 2 68 117 119 80 56 111 71 174 61 13 36 141 132 123 90 69 149 108 122 116 82 43 180 15...

result:

ok correct!

Test #28:

score: 7
Accepted
time: 1ms
memory: 7996kb

input:

199 2
1 106
198 165
176 34
59 39
1 34
151 36
78 85
1 109
48 4
1 13
165 1
73 163
159 126
150 106
1 33
82 103
17 180
1 151
46 87
1 111
195 1
1 164
25 23
135 161
1 107
1 2
11 58
97 1
170 1
71 57
72 157
1 158
1 186
153 1
1 60
29 1
27 52
50 1
162 122
64 1
95 1
1 75
160 142
134 81
77 155
79 1
1 119
30 169...

output:

101902858721
102
1 121 181 49 87 110 154 115 68 192 147 59 86 196 94 38 185 114 145 149 138 70 71 131 84 80 177 125 93 56 190 91 162 89 23 76 20 137 69 140 67 136 134 193 52 96 169 112 78 160 118 163 174 180 48 18 99 171 126 161 184 103 45 83 141 168 35 144 90 77 183 128 132 120 157 119 79 75 95 64 ...

result:

ok correct!

Test #29:

score: 7
Accepted
time: 2ms
memory: 12048kb

input:

197 2
24 1
65 24
129 58
92 96
61 1
42 18
95 3
167 168
147 110
2 172
143 156
115 110
1 67
158 127
99 134
126 89
30 95
85 13
1 149
128 106
81 118
137 100
146 88
105 1
76 105
153 9
96 123
67 49
61 186
1 9
120 46
51 79
79 1
77 195
17 11
117 7
114 106
135 21
59 1
100 122
179 67
158 184
16 83
96 1
191 75
...

output:

55959842378
56
1 181 78 133 23 161 95 90 195 162 106 40 21 99 36 118 2 187 197 7 58 182 108 17 46 167 29 53 16 169 13 188 93 88 143 42 158 126 75 100 10 110 121 96 59 79 9 105 149 67 61 24 32 163 107 97 

result:

ok correct!

Test #30:

score: 7
Accepted
time: 2ms
memory: 10036kb

input:

196 2
83 40
1 26
46 179
44 181
73 123
46 128
150 168
150 151
134 48
91 48
47 79
161 46
114 35
120 35
183 48
47 66
154 69
150 45
74 40
32 63
48 1
22 18
41 26
1 46
78 47
88 40
152 47
191 44
60 46
57 48
67 73
150 38
48 10
126 89
44 23
44 56
31 126
196 150
80 35
46 25
129 32
20 22
75 44
73 145
170 154
2...

output:

26055322292
42
1 189 106 102 2 111 37 8 5 193 54 65 158 129 63 32 40 73 47 44 22 35 126 154 46 48 26 150 124 109 115 15 104 166 98 135 93 196 38 45 151 168 

result:

ok correct!

Test #31:

score: 7
Accepted
time: 0ms
memory: 8020kb

input:

200 2
119 95
47 18
176 194
73 36
90 105
24 29
79 39
53 98
130 111
42 125
158 15
100 60
128 149
76 41
134 1
108 2
94 157
196 43
145 100
11 9
144 175
37 40
5 120
49 117
165 134
158 84
142 51
82 167
157 108
175 161
50 22
177 35
95 118
77 116
33 131
194 27
116 128
189 72
28 192
130 112
26 4
187 121
97 4...

output:

200000000000
200
1 165 89 121 61 9 173 56 20 69 6 198 191 175 32 39 27 176 148 52 181 99 73 13 192 23 15 84 71 188 140 98 64 43 50 87 156 109 72 159 25 37 82 68 55 26 104 136 47 129 143 7 116 149 141 14 5 21 138 97 164 80 118 119 174 107 178 146 126 145 60 172 131 16 83 114 3 44 193 125 115 62 92 94...

result:

ok correct!

Test #32:

score: 7
Accepted
time: 0ms
memory: 12084kb

input:

200 2
7 176
162 197
197 66
22 23
177 157
49 22
65 171
119 124
155 193
15 41
34 105
61 102
126 31
36 195
14 192
173 57
75 4
104 174
141 20
185 123
199 145
18 9
110 200
148 9
90 137
35 19
106 139
150 172
91 47
168 180
104 70
169 200
161 66
129 114
66 118
71 200
160 133
31 196
36 11
195 49
112 51
22 15...

output:

99918618520
200
1 65 102 24 199 183 34 81 137 150 124 68 170 74 73 11 195 198 22 55 188 109 91 159 173 154 19 83 86 129 63 33 139 108 160 100 194 134 193 136 64 187 200 80 111 44 175 141 54 3 31 87 28 78 15 98 12 178 9 69 4 95 104 5 142 128 132 153 14 177 130 39 66 79 162 158 85 48 138 17 30 143 27 ...

result:

ok correct!

Test #33:

score: 7
Accepted
time: 0ms
memory: 12136kb

input:

200 2
108 103
141 45
176 16
96 38
130 106
18 176
61 23
38 22
154 198
83 123
77 52
102 188
133 125
123 116
120 45
164 195
174 48
163 54
74 31
199 175
79 110
137 173
182 153
22 1
65 54
60 16
187 144
45 188
99 152
17 118
64 118
75 163
74 141
181 184
39 175
172 117
118 100
138 164
172 99
52 162
200 80
1...

output:

97817235416
200
1 3 76 55 38 192 112 66 174 2 127 61 99 40 168 117 19 178 78 187 180 15 151 47 200 160 128 60 176 105 90 93 134 10 179 108 133 98 183 140 118 86 104 106 81 150 88 87 25 42 147 49 123 70 119 28 173 185 56 153 142 53 162 77 197 167 91 92 199 156 171 39 154 89 94 121 181 26 190 95 110 2...

result:

ok correct!

Test #34:

score: 7
Accepted
time: 2ms
memory: 12192kb

input:

200 2
185 93
20 134
91 82
108 129
123 164
104 56
146 113
110 5
83 87
106 63
67 199
41 108
114 133
172 99
57 132
46 199
32 45
170 191
123 200
53 141
124 186
44 162
65 159
85 195
196 19
7 134
64 35
88 58
23 28
30 20
76 11
176 167
36 124
88 148
175 29
31 151
128 4
103 171
50 79
71 127
84 8
36 4
175 109...

output:

92546968269
200
1 70 137 78 161 40 147 179 109 33 56 104 175 111 86 29 14 72 153 177 168 197 83 87 73 38 146 113 67 126 65 159 199 66 13 46 16 122 18 62 51 181 80 74 171 125 98 103 188 55 85 195 20 160 6 30 134 116 35 64 7 68 99 172 102 118 71 127 136 101 52 120 157 22 176 167 91 144 48 193 82 156 1...

result:

ok correct!

Test #35:

score: 7
Accepted
time: 0ms
memory: 12068kb

input:

200 2
186 20
197 94
138 143
75 2
6 102
114 98
195 131
151 62
33 77
85 149
158 164
30 38
21 93
177 133
72 188
145 52
68 176
194 57
118 103
91 112
178 81
63 169
31 155
92 133
29 166
99 15
65 75
159 147
79 55
45 23
139 180
38 119
3 75
114 127
117 112
146 161
99 48
37 132
148 193
178 179
71 116
140 11
1...

output:

82875113284
152
1 75 103 35 118 3 64 33 183 113 150 184 46 96 19 191 182 5 157 49 37 175 132 115 84 57 161 53 86 146 119 136 16 105 141 142 38 12 151 40 62 47 30 11 102 160 6 140 27 55 167 50 120 79 83 131 67 22 90 195 130 23 68 101 176 185 61 158 116 154 71 124 156 171 152 129 56 174 92 169 177 32 ...

result:

ok correct!

Test #36:

score: 7
Accepted
time: 0ms
memory: 10024kb

input:

200 2
140 198
32 90
73 76
75 155
54 65
192 80
60 37
103 28
120 118
87 118
174 30
174 191
156 138
187 47
200 17
106 179
80 2
137 71
18 75
146 80
53 153
128 82
31 89
180 110
36 82
129 186
180 36
125 53
31 94
124 189
133 83
151 94
175 48
172 97
34 74
64 87
157 139
155 9
33 126
90 160
199 48
25 86
156 2...

output:

79408775618
143
1 140 129 136 91 143 186 130 76 62 158 132 145 92 164 53 189 154 194 124 125 68 16 86 23 46 25 141 40 89 94 152 127 151 31 65 190 134 184 147 197 54 38 139 74 70 84 34 66 166 60 83 183 111 88 133 52 174 165 77 56 176 10 55 99 168 114 169 13 135 96 90 200 182 8 17 14 167 48 126 3 50 3...

result:

ok correct!

Test #37:

score: 7
Accepted
time: 1ms
memory: 7852kb

input:

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

output:

31861270500
55
1 7 6 27 26 107 106 53 52 13 12 3 2 8 9 39 38 153 152 76 77 19 18 4 5 22 23 94 95 191 190 47 46 11 10 40 41 167 166 83 82 20 21 85 84 169 168 42 43 173 172 86 87 175 174 

result:

ok correct!

Test #38:

score: 7
Accepted
time: 2ms
memory: 12068kb

input:

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

output:

26748477707
43
1 13 11 12 106 105 104 35 37 36 4 3 2 19 18 17 154 153 152 51 52 50 6 7 5 48 47 49 148 147 146 16 14 15 133 132 131 44 46 45 136 135 134 

result:

ok correct!

Subtask #3:

score: 3
Accepted

Dependency #2:

100%
Accepted

Test #39:

score: 3
Accepted
time: 2ms
memory: 12076kb

input:

2000 2
1653 466
455 1262
319 394
823 998
1135 313
244 809
563 850
1865 1303
609 1531
302 1084
504 163
1475 1799
534 258
1597 413
1161 330
676 1694
1315 1619
1646 32
1629 161
280 1765
102 877
474 503
1162 491
1182 1505
532 1820
525 1836
1682 808
1026 80
809 1334
1376 1783
401 708
1323 1443
1242 1215
...

output:

176031446963
333
1 459 239 1438 410 1805 937 605 1479 1216 1818 313 1325 198 242 126 423 1142 1101 438 838 1471 1133 512 467 872 1100 915 1912 783 375 1719 142 877 435 1892 334 325 632 457 658 1411 1284 1870 1003 1574 82 374 18 287 482 525 1452 660 338 1208 148 1046 326 1161 1726 97 652 1919 1766 15...

result:

ok correct!

Test #40:

score: 3
Accepted
time: 2ms
memory: 12080kb

input:

2000 2
892 750
281 1593
1698 1268
1500 653
348 1393
1617 797
1044 680
1517 1883
1081 1003
293 948
412 478
1733 690
1785 1377
1902 1304
1674 1565
1350 131
242 573
1778 275
296 1177
1090 1862
1503 1175
1620 207
1441 323
181 449
219 1911
671 1713
606 1360
1558 834
562 1576
1212 1077
257 1606
790 1496
1...

output:

202483759818
403
1 1506 186 25 1577 563 629 762 1452 1100 687 381 801 1190 1638 36 1952 560 1461 1098 108 668 1095 1726 787 1042 772 1569 915 1068 430 552 1572 1384 348 1157 1393 784 1197 1868 1680 650 553 1787 1462 691 1287 1437 1798 1775 897 808 999 524 1199 1729 1586 439 1196 1792 651 1689 864 95...

result:

ok correct!

Test #41:

score: 3
Accepted
time: 2ms
memory: 12104kb

input:

2000 2
1581 867
670 1948
1286 1189
292 1357
1538 951
691 1646
502 1385
1071 812
482 469
1853 1303
614 774
363 62
506 91
718 951
1327 306
170 23
128 495
1841 263
178 588
271 252
930 1147
552 1150
1550 1584
685 1699
405 1353
1948 510
1632 327
1854 1167
1327 591
112 800
482 305
598 7
922 1645
1737 1811...

output:

184825610246
359
1 172 394 1959 1661 1191 1453 241 1449 1811 415 1773 934 13 1737 924 323 1152 1621 59 1304 670 936 324 1558 1810 598 510 1860 158 931 827 1630 1952 805 247 574 697 1491 1377 1484 336 1042 1609 1595 1891 647 254 1948 1032 1060 90 1041 86 1781 58 1770 992 3 1641 45 1655 839 1124 1711 ...

result:

ok correct!

Test #42:

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

input:

2000 2
1217 1905
1210 453
765 261
1635 1637
1867 1564
1876 1141
1867 283
1093 1385
677 1050
284 1377
228 1393
541 1985
884 242
1714 1304
118 15
1992 1098
449 181
1549 246
84 1198
913 1522
666 1685
1704 263
589 1407
1870 906
1411 561
1252 562
282 17
1137 372
764 1171
1721 172
1990 1755
1231 1948
201 ...

output:

222905521782
416
1 1544 1036 1958 1787 549 1655 1080 1617 1414 1901 763 830 189 1694 982 1290 1647 561 470 1932 1012 695 1411 1371 620 593 602 434 1986 257 813 83 1085 1457 100 1733 1899 1322 1554 1011 1974 1994 14 818 970 1340 5 1403 1213 687 1305 1072 193 1171 1043 215 372 1422 683 141 1970 1511 1...

result:

ok correct!

Test #43:

score: 3
Accepted
time: 2ms
memory: 12040kb

input:

2000 2
989 1552
460 285
670 1653
190 1210
736 941
1555 647
648 363
1500 1908
241 1143
1702 1181
266 1622
409 955
1442 1033
1236 447
194 1312
463 1304
1994 397
835 564
22 982
1214 562
813 1812
1396 783
191 1449
1760 691
103 1289
493 439
333 1401
283 884
1419 832
1561 277
1582 294
1183 925
7 529
191 1...

output:

176264452857
344
1 146 1542 397 680 376 1823 469 1734 1688 309 527 1497 1994 1766 618 384 30 742 4 22 1684 604 982 943 1136 1595 940 1798 1302 959 776 144 554 143 1547 1758 733 685 1333 1723 339 1299 1086 682 353 1166 1783 1517 657 129 662 1241 1594 343 531 96 522 1597 1733 1487 1300 190 510 857 182...

result:

ok correct!

Test #44:

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

input:

2000 2
1900 687
259 1748
582 1542
1844 470
1752 1845
202 37
1206 807
646 269
1687 681
1482 1630
930 446
391 617
1424 1798
1481 1762
820 295
1263 1766
474 210
372 1407
117 1854
199 216
1779 789
937 555
1494 1909
1824 1319
1001 1938
144 45
785 196
1135 636
390 1866
1404 206
1790 524
1734 663
1604 1767...

output:

362696256044
704
1 1488 461 1747 1234 1736 1316 324 1677 1366 1981 819 1350 448 1561 831 1149 1933 1698 1974 527 796 951 218 1450 1069 1398 869 920 1723 361 826 455 911 1188 1273 1363 1787 519 207 1493 55 1826 1567 1419 629 1646 125 697 1639 85 506 241 1759 862 159 651 1514 372 1964 1407 1572 1466 7...

result:

ok correct!

Test #45:

score: 3
Accepted
time: 2ms
memory: 12032kb

input:

2000 2
284 498
512 963
418 534
206 1186
1506 1397
1511 459
992 742
1644 1013
1474 1397
1942 1941
1673 1229
1384 442
1397 1756
1876 280
2000 1932
1397 1993
1217 1474
1774 1204
737 1785
1356 1384
1473 1116
2000 1812
1617 1739
17 1979
229 1979
723 492
621 227
358 550
206 376
440 1675
1393 1790
909 341
...

output:

203246075730
402
1 423 1610 1778 1248 532 1886 988 1047 87 15 104 1192 1672 437 277 530 1811 362 686 1737 1331 1606 932 140 927 1470 1619 1055 810 477 1467 1239 1004 1608 1009 1771 1084 1255 454 378 812 1142 1648 1961 847 1488 468 701 1638 1067 1876 183 890 983 1191 1994 696 1700 1950 1064 334 1242 ...

result:

ok correct!

Test #46:

score: 3
Accepted
time: 2ms
memory: 12136kb

input:

2000 2
1237 1826
571 1212
1932 1106
88 1218
764 916
1880 854
700 1803
585 679
891 1587
712 1921
233 738
668 1927
1167 918
432 1789
1377 1585
1344 916
692 1546
1749 1947
1571 1869
1484 1846
1531 1997
694 1957
758 567
1649 181
3 1062
987 1320
533 1487
1402 1085
936 1807
1526 752
183 1513
403 187
1796 ...

output:

404938855945
815
1 1556 348 1319 279 523 727 634 755 1272 175 1938 886 1429 1840 952 1315 1416 1914 198 1793 1311 613 200 796 812 1637 152 383 339 1002 1343 1522 535 392 364 210 1375 1304 178 370 1799 399 1967 938 287 1544 1716 121 442 1626 1043 734 1957 1723 911 581 1452 58 262 887 1194 231 846 258...

result:

ok correct!

Test #47:

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

input:

2000 2
593 1134
610 1128
274 1314
1799 123
1738 1823
523 1117
1272 529
1439 225
1275 450
286 1117
34 365
935 1460
1200 1008
475 1622
854 819
1632 890
996 1743
237 1665
1669 1985
1767 1934
1799 783
12 1601
342 1623
924 144
1269 146
1799 340
1280 1669
1270 1128
950 1245
1686 1730
1117 1202
178 393
180...

output:

273811282141
553
1 1344 766 1744 1791 1169 1720 403 1386 1219 627 1288 1524 1296 1910 237 1743 407 1337 592 967 1969 674 493 181 1000 582 199 438 52 1748 1559 1051 1162 903 577 812 129 1617 1793 435 1348 1126 602 573 334 1380 795 1018 641 226 1332 1685 1142 912 729 70 317 968 1501 1976 225 1154 1998...

result:

ok correct!

Test #48:

score: 3
Accepted
time: 2ms
memory: 8196kb

input:

2000 2
1383 1
1 1410
1 1106
1154 1
1 1202
1794 1
1512 1
1744 1
221 1
1 917
1637 1
1 118
1 423
164 1
1 1881
479 1
1 1029
1 567
1 193
1 1364
1 45
1458 1
692 1
1765 1
807 1
897 1
43 1
1243 1
1 681
1272 1
1 579
122 1
1 1241
1299 1
1558 1
1 88
726 1
1 654
1900 1
1895 1
1 384
1 661
223 1
1 956
1 1112
38 1...

output:

981828873758
2000
1 1038 380 258 1977 1806 1187 574 1967 1396 1899 396 1601 651 1105 1961 132 1398 1377 800 882 1078 215 264 942 1697 543 709 784 1699 232 436 278 315 620 444 404 1760 1379 12 998 187 191 1083 1691 1375 993 159 1343 1738 1662 958 607 669 1782 1632 746 442 1892 1679 1021 1477 1754 168...

result:

ok correct!

Test #49:

score: 3
Accepted
time: 3ms
memory: 12084kb

input:

1999 2
1 1197
761 1416
1 1777
1341 30
1 791
966 1025
1 890
1103 1
1195 1929
342 1
219 1
993 553
1 1308
392 726
993 1
1747 777
840 1
1 1977
916 1
1 8
1 447
1125 1740
493 1153
781 762
1 435
1 1939
1965 1030
1 812
1 1962
162 1568
793 82
1208 1087
938 1
1 1512
480 1361
1 957
636 816
56 1585
1 822
1018 1...

output:

1001116296577
1002
1 547 771 1921 1840 1244 1194 14 1642 291 1825 1503 1286 1485 1579 1348 817 1231 529 661 1385 1157 626 1267 490 891 479 270 1151 603 1534 785 963 973 484 1769 1323 371 40 278 207 1248 261 53 1148 1252 1189 255 688 1805 807 1621 743 745 1656 798 1951 1993 562 1097 742 1334 74 582 8...

result:

ok correct!

Test #50:

score: 3
Accepted
time: 2ms
memory: 12108kb

input:

1997 2
1471 500
206 950
1847 634
897 1
1227 1
435 1540
1020 5
1058 1810
888 1947
1504 1339
1899 986
1647 1604
1 1836
997 261
1349 1153
965 1
429 1
4 1133
1154 259
1993 1
1760 609
8 1
1 1639
1114 1901
1888 971
969 706
1910 875
1561 1888
1118 40
1 372
860 1849
1 1784
1 330
1521 1951
1354 6
1798 375
12...

output:

505561828143
506
1 1295 1833 302 1752 1342 398 1823 1815 798 1702 967 1906 1386 51 874 289 1041 1179 1731 939 674 1055 649 294 709 1016 1685 1368 1782 193 1441 1867 207 11 439 1426 1327 1449 975 1411 988 1595 1513 1157 858 921 1632 1566 1251 641 1495 1472 759 335 220 1091 1279 1704 1574 679 460 1888...

result:

ok correct!

Test #51:

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

input:

1936 2
91 782
1865 1244
427 448
1608 1299
1644 880
5 1509
232 1110
1515 1927
1257 448
1217 1331
1 363
1131 1217
1849 1608
1928 249
482 1384
445 682
274 1075
1283 508
1515 1189
1250 1588
529 1158
1833 1217
1064 968
1746 948
264 1509
1369 92
1865 1395
1369 1312
969 1109
1895 333
955 682
1291 275
1369 ...

output:

72540612666
132
1 1500 778 1241 145 1387 1344 905 1520 1016 420 1516 276 1910 1219 1224 1281 248 1734 1022 1346 1581 1005 1118 219 1816 961 135 673 1867 1560 793 941 701 1620 1400 1205 904 536 1884 1742 1300 1659 955 445 682 1283 2 1145 333 977 969 1588 482 1432 1158 504 1865 1138 1291 448 837 1051 ...

result:

ok correct!

Test #52:

score: 3
Accepted
time: 2ms
memory: 10564kb

input:

2000 2
1142 984
741 1666
929 727
870 1390
111 797
486 816
974 1047
1836 1891
1942 1457
1730 1121
784 1586
881 1069
809 1611
1749 1483
269 1298
1435 1988
59 549
1663 1161
526 1785
445 1934
1604 562
1494 1070
334 332
1028 723
574 1933
1676 1670
1316 1613
1055 490
1321 1549
1374 83
23 497
796 210
728 1...

output:

2000000000000
2000
1 163 1352 1563 1614 788 48 1167 921 1378 634 1514 286 1743 998 1749 1181 1784 540 650 1144 1892 216 764 1876 192 1954 1416 574 1596 1909 58 1198 1693 1709 1348 327 1507 902 932 123 350 275 674 1803 1072 885 828 1171 296 1606 829 1699 980 894 1694 996 1133 1980 1208 1241 866 703 9...

result:

ok correct!

Test #53:

score: 3
Accepted
time: 2ms
memory: 10336kb

input:

2000 2
450 1099
1291 492
1509 508
1606 702
1878 729
1405 58
430 1790
829 737
1424 1560
488 1944
1366 1611
128 607
1935 477
1364 1359
1964 578
471 1112
995 420
405 340
1058 1297
526 1263
527 1557
512 1599
1012 1340
1776 558
1202 1515
1835 277
1219 1610
898 116
625 1123
232 1492
1780 71
722 1280
177 6...

output:

1010476018711
2000
1 555 654 1537 679 404 1178 1167 1651 1974 572 1176 1984 297 997 1995 1823 800 1012 1285 239 347 1813 9 624 1181 1997 1640 1989 633 525 370 362 1793 14 500 1905 728 663 1159 1407 688 291 1664 1397 1476 428 863 1504 887 1264 1312 1105 1637 701 1797 1654 604 644 1297 1046 462 504 12...

result:

ok correct!

Test #54:

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

input:

2000 2
1280 733
1348 842
180 1085
492 865
1924 698
646 249
1106 232
1819 1637
1785 585
673 460
799 1613
955 1512
781 1331
1926 699
518 1314
240 433
1217 346
1819 628
140 1858
1910 854
588 1031
231 582
718 230
1600 1880
1304 471
655 1330
1817 1233
1297 304
1466 113
518 465
14 141
1653 506
31 1557
199...

output:

994437083657
2000
1 54 725 1310 1698 329 874 658 722 1481 275 357 36 182 644 1928 1221 1293 1302 201 757 1838 1681 297 1649 1395 903 1231 1431 954 846 1739 1864 607 1066 927 1165 1647 1963 1351 1144 1753 525 1579 401 853 1938 1245 966 1372 84 1316 1592 1498 1063 1463 1472 1038 1972 489 72 1750 1220 ...

result:

ok correct!

Test #55:

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

input:

2000 2
1033 409
609 267
1734 507
588 1257
112 1620
844 1436
25 599
36 324
583 163
922 286
67 268
1767 720
961 1569
553 239
99 1795
1391 1138
689 1452
1250 953
1260 1794
251 1788
1891 1726
1414 77
689 810
42 389
1688 1957
1799 892
798 1790
612 927
999 582
566 879
1603 741
1153 1356
1998 1288
1993 151...

output:

1011568611012
2000
1 573 690 1630 29 1069 1308 271 1605 223 1388 957 1513 826 1223 1700 672 1158 59 1682 495 576 1015 900 1787 858 1245 366 1001 1741 217 33 1797 1397 219 1471 444 438 1731 1501 911 776 1808 1295 1572 944 1085 1186 708 1286 65 1109 553 1067 1739 239 297 959 1892 542 1565 1494 979 112...

result:

ok correct!

Test #56:

score: 3
Accepted
time: 2ms
memory: 10180kb

input:

2000 2
1213 910
748 565
244 1508
69 1383
1066 1452
1470 20
953 273
926 226
1647 1709
378 1921
1809 1976
1714 1640
1273 1888
1243 591
1277 1937
416 491
1360 367
242 131
819 192
307 1792
1497 317
1710 1547
129 55
457 1380
1046 1331
1397 954
740 1994
1388 1649
819 312
1168 694
713 914
1917 928
979 1671...

output:

804671840202
1502
1 95 1136 1846 400 1915 98 1029 335 1756 1576 511 102 865 1265 1363 1997 589 345 850 1285 464 343 190 719 352 434 383 1808 1909 695 172 414 985 704 1863 1347 487 249 1045 1204 948 1836 851 1542 558 1405 217 1875 1792 1337 135 1231 488 219 587 1717 1642 1676 947 1381 933 372 974 89 ...

result:

ok correct!

Test #57:

score: 3
Accepted
time: 2ms
memory: 12192kb

input:

2000 2
583 1761
646 880
265 1017
669 1241
1606 1517
1791 1712
1199 1024
1939 161
1888 1095
1127 1892
169 1741
1411 627
1932 709
201 1642
1695 1359
1853 34
1597 1117
1629 907
392 1684
247 32
75 1518
1990 1150
1465 878
304 186
288 432
49 1221
406 1738
99 191
1125 1264
903 1572
1493 1804
1783 1402
645 ...

output:

771091486166
1403
1 656 91 1915 1340 1748 723 736 812 1804 1826 999 1493 672 1710 275 98 1368 1490 1833 31 1255 1990 172 842 1737 1752 1225 1741 444 1296 674 594 248 1980 169 331 1437 182 721 847 1104 1089 188 36 852 1196 1859 1170 668 1888 1402 1438 329 1783 1095 308 910 1439 437 18 1943 1295 1775 ...

result:

ok correct!

Test #58:

score: 3
Accepted
time: 2ms
memory: 12148kb

input:

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

output:

73323472678
111
1 4 5 20 21 85 84 339 338 1355 1354 677 676 169 168 42 43 10 11 2 3 14 15 61 60 243 242 968 969 1939 1938 484 485 121 120 30 31 7 6 26 27 111 110 441 440 1763 1762 881 880 220 221 55 54 13 12 50 51 207 206 825 824 1649 1648 412 413 103 102 25 24 97 96 387 386 1547 1546 773 772 193 19...

result:

ok correct!

Test #59:

score: 3
Accepted
time: 2ms
memory: 12140kb

input:

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

output:

50545980022
85
1 10 9 8 76 75 74 667 666 665 1996 1995 1994 222 223 221 25 24 23 3 4 2 22 20 21 189 188 190 1714 1713 1712 571 570 569 63 64 62 7 6 5 46 44 45 403 401 402 1207 1206 1205 134 136 135 15 14 16 142 141 140 1258 1257 1256 419 421 420 47 48 49 439 437 438 1315 1314 1313 146 148 147 1321 1...

result:

ok correct!

Subtask #4:

score: 4
Accepted

Dependency #3:

100%
Accepted

Test #60:

score: 4
Accepted
time: 61ms
memory: 23408kb

input:

200000 2
71973 76326
97670 168508
171244 5932
115231 147408
128416 153589
19744 26807
67878 98255
22662 194128
198320 150303
86723 49603
10517 32984
185691 125147
174597 24994
81050 42404
165800 182920
89285 145179
128551 33017
183430 8057
41020 176174
198318 18811
152231 31881
114181 60045
29558 13...

output:

882399295740
1706
1 188460 70658 125662 114345 13738 118312 88056 86342 20469 125150 198830 34184 171733 146149 125185 31328 183607 39714 188755 19094 25207 103823 85783 175419 113506 128306 94524 166905 85349 66259 179243 172850 177196 32772 121935 14671 116967 128380 28309 126355 23520 182363 4470...

result:

ok correct!

Test #61:

score: 4
Accepted
time: 66ms
memory: 21048kb

input:

200000 2
32082 187519
5208 145093
50076 154772
187374 120564
139957 35735
23362 7323
91085 172598
85906 42406
71445 72269
152408 175847
109126 170295
57424 51948
142288 190335
46434 27012
196277 147605
116314 115538
181190 11940
23862 22122
71611 183053
142917 98634
45954 4192
110819 169037
49947 10...

output:

833023647871
1601
1 168670 74461 42679 47846 197507 193300 176275 43467 92511 166695 180727 39799 146165 23625 27565 169208 102454 199030 33416 53139 41207 140499 173852 107708 160947 24046 162828 137147 29429 166803 83672 44352 43797 155400 122620 171907 112784 162293 35384 35944 17828 107033 16068...

result:

ok correct!

Test #62:

score: 4
Accepted
time: 68ms
memory: 23328kb

input:

200000 2
78638 58642
112962 25496
85068 25026
70130 61586
173031 26076
136367 101291
127709 139920
71308 101369
136151 162399
15899 42470
188783 14739
148981 125658
63825 51000
43025 32262
1942 892
186758 34888
111721 75954
15727 114535
43402 80763
159252 40071
178432 174508
140837 145658
110251 183...

output:

859520154059
1660
1 21614 191534 25670 125446 196343 140446 187768 45970 18992 27859 121704 100825 54900 148400 79538 10573 89131 27182 144926 789 178645 5432 190456 44197 136394 68411 65945 174946 56339 66095 170879 37838 156697 99192 142052 190483 37254 124057 135100 43408 22149 46668 179674 28750...

result:

ok correct!

Test #63:

score: 4
Accepted
time: 72ms
memory: 23456kb

input:

200000 2
113130 116994
199787 127733
175019 81432
178540 179218
84082 127210
163623 155486
189624 73275
82498 8202
61848 113067
100558 173153
127108 94716
127580 54314
147631 53398
105967 1535
32421 100984
28479 170565
50049 13612
128342 24121
161245 52286
199917 196293
126521 9391
115032 50698
4507...

output:

942852419968
1789
1 54853 35470 18260 184539 180649 4032 114891 43965 100566 118876 187170 85974 11834 2432 30455 157244 114806 47521 106938 22337 67473 148648 122055 185951 23492 71377 26493 92332 151083 29807 192004 46667 54419 101756 152250 150005 90820 174399 87993 28631 44374 157784 154481 7588...

result:

ok correct!

Test #64:

score: 4
Accepted
time: 62ms
memory: 20864kb

input:

200000 2
77664 54637
84144 154928
72506 50449
160113 77853
194182 38791
107483 80245
9315 30663
148025 33975
102823 42879
52529 135121
22346 28336
97279 42789
117070 88657
79123 108461
132766 124070
106264 167067
191149 170038
150680 124017
122526 80240
22015 134260
180496 175307
74449 114090
104518...

output:

1171517212692
2265
1 102983 154271 97112 10816 170812 9666 71235 136548 1981 158535 115214 17610 34582 30341 74635 139749 32416 54904 21027 164065 131128 194069 162611 110282 26732 141731 47965 8644 62396 94646 27065 12865 61499 8199 191102 160142 31048 149413 52987 199682 80077 31632 31643 165244 8...

result:

ok correct!

Test #65:

score: 4
Accepted
time: 74ms
memory: 20904kb

input:

200000 2
28934 176056
136164 196254
31381 23123
25526 108297
57361 64966
190533 45227
74484 164959
28842 2327
81570 179755
188864 38342
104303 102044
136042 74199
171111 80778
111330 158089
52128 170798
101490 145339
120609 82326
173031 112314
73010 112478
119847 138176
122774 4868
42346 105059
3350...

output:

2326744528710
4529
1 80499 102953 171795 5416 133398 167604 114380 111518 50573 134654 93720 38805 93951 186882 63808 85082 86520 125125 87227 98497 20045 77886 83457 59467 94418 197201 120314 181605 76794 48819 37714 180991 48145 127620 116899 162364 165395 22723 66442 105664 43079 167324 101407 44...

result:

ok correct!

Test #66:

score: 4
Accepted
time: 77ms
memory: 20968kb

input:

200000 2
56021 51529
68684 59222
42913 113684
79211 108152
31389 101993
34308 149833
158947 72984
107009 139522
86949 11829
111788 59214
112750 12966
27645 157963
59289 59222
139737 47437
145601 58355
32220 146798
111541 185862
25607 45580
152343 179102
72458 111092
176999 19531
66379 119683
76547 1...

output:

767459126849
1505
1 40108 94103 22245 122180 24843 3298 102299 81892 130324 26284 190184 110511 130386 89005 117443 158376 187861 199963 164216 75465 17927 129974 158581 147829 160579 40243 99185 7115 49535 10260 188401 196629 62528 4487 83620 163739 22977 9328 114969 177828 29679 183821 78391 69616...

result:

ok correct!

Test #67:

score: 4
Accepted
time: 61ms
memory: 23428kb

input:

200000 2
104390 122869
25883 142866
160515 43820
128440 13022
8318 136414
157868 188440
156836 187687
167016 9347
39806 182142
179923 72411
45877 114238
114548 82833
40280 113331
69170 31456
118069 101689
177443 61482
19872 186357
168183 107559
61588 170900
16642 45648
747 57401
94126 173098
136686 ...

output:

3675388620625
7158
1 156746 25359 182551 171456 6217 58698 76669 46957 104140 81229 107564 43096 196087 49741 18405 71606 68862 169469 46140 17284 3806 60578 21865 49934 124696 98544 96209 186730 73717 120868 172295 37265 148274 117606 53755 167968 145692 11307 151374 3959 82355 73614 35810 173849 1...

result:

ok correct!

Test #68:

score: 4
Accepted
time: 79ms
memory: 23112kb

input:

200000 2
109985 87619
37980 22189
97113 50655
141404 55232
147996 65598
36748 174192
131854 177776
18218 47619
13160 113823
86872 169443
90387 198777
81052 158293
27515 37979
198311 51356
166249 142601
91346 8372
139757 47600
133114 143533
186906 52882
52043 134177
106749 3786
33870 108458
116250 23...

output:

992123589063
1945
1 149879 157597 68194 177461 33891 79697 68309 7999 134398 169063 5478 165771 6368 125738 14108 75395 57884 30271 173965 91734 55151 79670 55322 51597 177884 150114 87114 112290 11053 177705 196339 8492 134678 47748 49903 180074 22901 11300 30067 99488 63779 457 198776 146469 10285...

result:

ok correct!

Test #69:

score: 4
Accepted
time: 61ms
memory: 20860kb

input:

200000 2
100522 147187
54889 185960
38949 138090
86106 80207
27403 199320
146820 181967
134302 13313
25408 138672
72842 34248
161006 103810
196273 40476
105432 101143
194952 131699
159995 85132
78133 40501
20116 1846
85728 109828
53166 107050
53317 170563
49857 175255
156370 158685
46487 66693
85983...

output:

3540743394022
6910
1 46821 16382 23365 146371 194290 153311 150697 168802 26336 159465 158012 103012 94377 116421 107276 105006 146400 59201 8935 174594 42636 63889 94029 62947 161170 4124 176587 199890 35236 33953 48870 8028 36632 175495 135353 95125 84748 89771 74192 181238 155630 57348 132154 140...

result:

ok correct!

Test #70:

score: 4
Accepted
time: 65ms
memory: 20820kb

input:

200000 2
89710 128357
3426 66417
52472 91874
31627 100433
198960 160902
176265 76059
70560 72724
139051 191341
512 111102
120209 75664
15138 126122
197008 153163
179022 152817
2515 43991
27182 1020
128784 150584
143001 48543
24479 138105
188695 57568
93380 190780
71186 124797
159152 141009
21133 382...

output:

1337020465724
2654
1 71889 191226 19292 82451 49694 196313 188096 99045 62799 16371 17992 4905 17321 41263 121487 10567 162466 78068 189039 25895 22213 69046 98109 80688 176796 139665 199121 182054 26232 3871 117732 54720 199868 30987 102418 81037 182692 172615 103594 92785 118071 39196 164166 94545...

result:

ok correct!

Test #71:

score: 4
Accepted
time: 203ms
memory: 29856kb

input:

200000 2
1 121764
151707 1
1 146498
120892 1
1 167954
37051 1
65946 1
142412 1
1 33774
134506 1
163786 1
1 175250
1 164690
159445 1
1 60645
1 1330
139128 1
121091 1
17510 1
89422 1
20081 1
1 172899
177661 1
1 172826
1 43543
1 177837
28825 1
1 120168
1 38254
1 8601
58920 1
147872 1
1 41335
1 164269
1...

output:

99770036814555
200000
1 140621 116188 7583 180413 12340 17856 77879 53481 138582 144425 77443 49402 33431 62446 164664 18037 72484 97 132173 30110 79080 146059 41876 129823 91924 50210 187487 197443 129284 16523 67124 100491 189934 61418 161782 168141 181201 20758 95545 99344 90841 195259 198417 980...

result:

ok correct!

Test #72:

score: 4
Accepted
time: 120ms
memory: 22944kb

input:

199999 2
67072 1
92171 150753
90888 151980
49069 30219
174222 9855
195658 1
1 87942
77002 134696
1 65126
109947 3424
145914 162383
1 2757
1 112019
164258 1
66908 62514
185957 1
122946 13227
1 18985
173656 190833
1 102891
1 6832
47914 29907
184372 1
177178 1
174467 87761
132840 1
145220 137302
1 1590...

output:

99914041431818
100002
1 135761 71359 165486 96078 123209 143064 4831 142337 112037 75423 153915 157019 139776 146924 133506 61682 107291 19552 98235 37069 152999 94543 173666 65321 25006 11671 84198 89842 124082 33031 116729 84176 173347 23035 44721 43722 160010 149387 5272 88791 166376 60973 174072...

result:

ok correct!

Test #73:

score: 4
Accepted
time: 93ms
memory: 19092kb

input:

199997 2
181667 73912
70196 155617
57266 177774
146844 22851
17625 44807
140237 145179
71321 26122
119873 142655
42888 1
1 12665
2354 21037
157498 117106
154042 78181
9589 1
46002 137008
19680 124524
133338 79920
1 118916
65513 53811
163778 43702
29017 144717
98739 157944
189251 183682
182803 178046...

output:

49962213918134
50006
1 2544 180804 177685 149002 139296 196648 55349 12190 31271 3694 37517 49218 166081 190442 39005 26297 72130 52814 197082 195945 198234 52340 38121 84222 74802 73841 106509 162212 185226 126357 87158 45960 5240 107421 26101 172923 98448 195242 77810 142984 170834 25320 166787 66...

result:

ok correct!

Test #74:

score: 4
Accepted
time: 92ms
memory: 16604kb

input:

199809 2
169878 4225
23345 92377
98479 42575
149948 72420
50892 90193
47118 16414
69072 47907
48571 63127
149065 40766
143982 72205
169350 85345
154664 137516
154095 72685
95325 102444
101466 119755
32299 39632
58986 95625
177381 137516
36382 110945
69668 129015
97533 177853
32749 35220
121826 30883...

output:

713049791453
1341
1 850 28452 40415 120646 167701 158642 126377 82063 21050 17693 75852 85889 128769 117678 102773 127248 163670 77196 27141 177633 72404 137599 36029 68157 189021 37164 85489 166942 136650 106937 185841 182683 41803 50810 7016 17021 102647 8435 40679 136824 35738 119298 127369 14835...

result:

ok correct!

Test #75:

score: 4
Accepted
time: 83ms
memory: 65760kb

input:

200000 2
5189 138698
162040 22588
64703 112781
3394 136450
174354 3779
21094 6916
88534 109117
134528 32716
199107 74065
151148 26217
128242 194757
185664 167983
19773 60770
11507 105959
161807 139962
38366 176916
185209 97924
54025 141961
190880 55231
43069 120905
94677 20549
79285 158427
82389 310...

output:

200000000000000
200000
1 25853 99641 128636 58204 141207 117428 83196 159851 50501 148078 171178 174465 152787 128200 123590 40903 33704 77459 55723 195405 17655 51742 93318 107382 32855 19461 177111 85255 87913 110545 126408 70810 106264 63366 40557 58252 101022 174011 146107 92155 55819 116286 108...

result:

ok correct!

Test #76:

score: 4
Accepted
time: 88ms
memory: 43344kb

input:

200000 2
27363 14113
105695 61177
18014 22956
18808 177624
148980 14330
95219 115023
116364 74015
136966 188653
121569 4887
83271 90316
84619 130170
84529 45369
23977 192773
175001 80000
73676 20454
99853 7287
177160 58905
36849 94281
58588 29241
657 180060
2293 174820
128219 100022
88580 55357
1264...

output:

99922046309746
200000
1 47452 153804 145599 83548 135694 3575 163018 109084 74689 33496 131873 91026 88821 188955 73754 38412 43771 66809 55414 109232 108676 62426 13452 53525 115508 146372 63181 87851 107697 168848 132893 24691 87775 105179 71317 139728 19514 76296 160899 5857 185495 78129 196012 1...

result:

ok correct!

Test #77:

score: 4
Accepted
time: 88ms
memory: 33168kb

input:

200000 2
100468 181493
53969 172322
75135 130909
139964 194504
19021 125659
37607 9557
72510 180054
167286 130071
45448 136281
73858 61335
140036 142670
159885 42363
154039 91451
37090 97684
45858 15964
98746 33430
68396 72322
29978 140827
33566 154533
157183 98893
184791 130026
39154 3812
132886 59...

output:

100057925839612
200000
1 182996 173538 68939 142523 193015 137544 79260 117911 6670 174754 176303 126340 26071 91927 148688 125622 150624 94540 179828 118214 72941 149649 141865 8401 67709 1617 21650 63355 38271 88555 96967 65505 156990 38621 185999 91821 5482 6122 198172 193846 58761 160778 28838 5...

result:

ok correct!

Test #78:

score: 4
Accepted
time: 57ms
memory: 32220kb

input:

200000 2
171220 164313
198029 73747
26096 85012
110214 89139
172790 175093
171731 30080
69767 9015
141703 177975
79195 71430
44626 160824
146861 163709
156800 76389
19445 181416
113267 89896
124839 30054
80809 151537
99873 187186
100638 166286
44321 120253
183612 28877
15242 180944
89632 190302
6708...

output:

99911380218441
200000
1 165115 49359 74567 110902 90003 50086 61841 179907 93501 158123 18507 174986 153696 17756 128199 80988 198396 114565 22083 131204 188226 27651 35685 72521 66728 92098 135609 95306 144381 75124 66938 127386 7997 112758 134995 152766 95415 174294 26783 132532 103242 99483 89332...

result:

ok correct!

Test #79:

score: 4
Accepted
time: 70ms
memory: 27040kb

input:

200000 2
8314 177328
146834 168561
24273 99494
153115 63830
166298 9934
167286 101744
109715 98447
784 143770
22271 37823
83151 28850
174199 89913
24577 115223
149285 39182
5074 9380
197079 150501
121534 133095
191134 195404
60411 87734
182665 135214
187189 119252
166358 54195
156812 155428
18144 19...

output:

80866474815147
150002
1 81709 27495 161651 51720 144385 777 72674 132921 127681 61334 170860 159326 71316 139005 118114 112873 15221 47510 29559 92531 145893 76612 71572 73238 18113 23874 134330 55096 111676 70015 806 113662 8384 44707 96493 160968 140462 29862 173965 192411 140921 120551 140689 176...

result:

ok correct!

Test #80:

score: 4
Accepted
time: 77ms
memory: 26136kb

input:

200000 2
169179 38103
45411 72139
139020 184462
125323 167101
163401 46625
97240 145227
77416 13783
135642 68825
116351 57737
32614 100924
171164 135235
123336 159074
118178 33394
108090 135019
128087 172240
108313 170956
27543 69102
7341 141209
190919 35931
38512 119039
191316 21753
70270 112143
19...

output:

75697889479414
140003
1 7593 123209 199714 26824 147004 20568 144457 11617 22999 83291 85957 129351 183777 115533 62588 44152 192129 105918 119533 27845 91404 199835 157136 163990 151007 100209 8348 191421 66318 172397 153526 162642 133696 92994 35462 75896 122045 112534 93694 110727 14171 35342 862...

result:

ok correct!

Test #81:

score: 4
Accepted
time: 33ms
memory: 18372kb

input:

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

output:

208672979041
307
1 7 6 25 24 96 97 391 390 1560 1561 6247 6246 24984 24985 99943 99942 199885 199884 49971 49970 12492 12493 3123 3122 780 781 195 194 48 49 12 13 3 2 8 9 38 39 158 159 636 637 2548 2549 10197 10196 40787 40786 163145 163144 81572 81573 20393 20392 5098 5099 1274 1275 318 319 79 78 1...

result:

ok correct!

Test #82:

score: 4
Accepted
time: 39ms
memory: 18900kb

input:

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

output:

135510774019
199
1 6 5 7 60 59 61 552 551 553 4978 4977 4976 44785 44783 44784 134353 134352 134351 14928 14929 14927 1659 1660 1658 184 183 182 20 22 21 2 4 3 27 26 28 256 254 255 2296 2295 2294 20650 20649 20648 185830 185829 185828 61943 61945 61944 6883 6882 6881 765 766 764 85 84 83 9 10 8 75 7...

result:

ok correct!

Subtask #5:

score: 0
Wrong Answer

Test #83:

score: 0
Wrong Answer
time: 1ms
memory: 5808kb

input:

2000 3
1359 90
1703 163
158 188
360 1501
195 664
1414 215
1546 1756
536 1096
1726 1223
1150 104
1757 703
1982 282
1023 998
1180 419
576 1759
1496 1993
44 670
1703 952
855 849
1998 1399
1280 980
1533 1090
1270 678
1680 387
469 1734
1799 263
473 588
303 226
5 295
1489 1471
1094 1667
1912 210
1368 1360...

output:


result:

wrong output format Unexpected end of file - int64 expected

Subtask #6:

score: 0
Skipped

Dependency #5:

0%