QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#523726#1142. Fountain Parksgreen_gold_dog#30 523ms53212kbC++203.7kb2024-08-18 17:01:292024-08-18 17:01:29

Judging History

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

  • [2024-08-18 17:01:29]
  • 评测
  • 测评结果:30
  • 用时:523ms
  • 内存:53212kb
  • [2024-08-18 17:01:29]
  • 提交

answer

#include "parks.h"
#include<bits/stdc++.h>

using namespace std;

typedef int ll;

struct DSU {
	vector<ll> p;
	DSU(ll n) {
		p.resize(n);
		for (ll i = 0; i < n; i++) {
			p[i] = i;
		}
	}
	ll get(ll a) {
		return (p[a] == a ? a : p[a] = get(p[a]));
	}
	void unite(ll a, ll b) {
		p[get(a)] = get(b);
	}
};

ll construct_roads(vector<ll> x, vector<ll> y) {
	ll n = x.size();
	map<pair<ll, ll>, ll> all;
	for (ll i = 0; i < n; i++) {
		all[make_pair(x[i], y[i])] = i;
	}
	vector<vector<ll>> to(n);
	vector<ll> m1;
	for (ll i = 0; i < n; i++) {
		if (all.find(make_pair(x[i] + 2, y[i])) != all.end()) {
			if (all.find(make_pair(x[i] + 2, y[i] - 2)) == all.end() || all.find(make_pair(x[i], y[i] - 2)) == all.end()) {
				to[i].push_back(all[make_pair(x[i] + 2, y[i])]);
			}
		}
		if (all.find(make_pair(x[i], y[i] + 2)) != all.end()) {
			to[i].push_back(all[make_pair(x[i], y[i] + 2)]);
		}
		if (all.find(make_pair(x[i] - 2, y[i])) != all.end()) {
			if (all.find(make_pair(x[i] - 2, y[i] - 2)) == all.end() || all.find(make_pair(x[i], y[i] - 2)) == all.end()) {
				to[i].push_back(all[make_pair(x[i] - 2, y[i])]);
			}
		}
		if (all.find(make_pair(x[i], y[i] - 2)) != all.end()) {
			to[i].push_back(all[make_pair(x[i], y[i] - 2)]);
		}
	}
	set<pair<ll, ll>> have;
	vector<ll> u, v, a, b;
	DSU d(n);
	for (ll i = 0; i < n; i++) {
		for (auto j : to[i]) {
			d.unite(i, j);
			if (have.find(make_pair(j, i)) != have.end() || have.find(make_pair(i, j)) != have.end()) {
				continue;
			}
			u.push_back(i);
			v.push_back(j);
			have.emplace(i, j);
			ll bx = (x[i] + x[j]) / 2, by = (y[i] + y[j]) / 2;
			ll add = 1;
			if ((x[i] + y[i]) % 4 == 0) {
				add = -add;
			}
			if (x[i] == x[j]) {
				add = -add;
				if (y[i] < y[j]) {
					add = -add;
				}
				if (x[i] == 2) {
					add = -1;
				}
				if (x[i] == 6) {
					add = 1;
				}
				bx += add;
			} else {
				if (x[i] < x[j]) {
					add = -add;
				}
				by += add;
			}
			a.push_back(bx);
			b.push_back(by);
		}
	}
	set<ll> aa;
	for (ll i = 0; i < n; i++) {
		aa.insert(d.get(i));
	}
	if (aa.size() > 1) {
		return 0;
	}
	build(u, v, a, b);
	return 1;
}

#ifdef LOCAL
static void check(bool cond, string message) {
        if (!cond) {
                printf("%s\n", message.c_str());
                fclose(stdout);
                exit(0);
        }
}

static int n;
static bool build_called;
static int m;
static vector<int> _u, _v, _a, _b;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
        check(!build_called, "build is called more than once");
        build_called = true;
        m = u.size();
        check(int(v.size()) == m, "u.size() != v.size()");
        check(int(a.size()) == m, "u.size() != a.size()");
        check(int(b.size()) == m, "u.size() != b.size()");
        _u = u;
        _v = v;
        _a = a;
        _b = b;
}

int main() {
        assert(scanf("%d", &n) == 1);
        vector<int> x(n), y(n);
        for (int i = 0; i < n; i++) {
                assert(scanf("%d%d", &x[i], &y[i]) == 2);
        }
        fclose(stdin);

        build_called = false;
        const int possible = construct_roads(x, y);

        check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
        if (possible == 1) {
                check(build_called, "construct_roads() returned 1 without calling build()");
        } else {
                check(!build_called, "construct_roads() called build() but returned 0");
        }

        printf("%d\n", possible);
        if (possible == 1) {
                printf("%d\n", m);
                for (int j = 0; j < m; j++) {
                        printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
                }
        }
        fclose(stdout);
        return 0;
}
#endif

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

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

input:

ba73dbf9c7d5e5202834d6a500541c
1
2 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
0

result:

ok 

Test #2:

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

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 2
2 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
1
0 1 1 3

result:

ok 

Test #3:

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

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 2
2 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #4:

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

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 2
2 4
2 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 1 1 3
1 2 1 5

result:

ok 

Test #5:

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

input:

ba73dbf9c7d5e5202834d6a500541c
4
2 2
2 4
2 6
2 8

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
3
0 1 1 3
1 2 1 5
2 3 1 7

result:

ok 

Test #6:

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

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 2
2 4
2 8

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #7:

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

input:

ba73dbf9c7d5e5202834d6a500541c
4
2 2
2 4
2 8
2 10

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #8:

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

input:

ba73dbf9c7d5e5202834d6a500541c
4
2 2
2 4
2 6
2 10

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #9:

score: 5
Accepted
time: 167ms
memory: 26200kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
2 15660
2 23918
2 132200
2 117654
2 162750
2 183010
2 75554
2 29740
2 185476
2 135138
2 194024
2 182274
2 1338
2 42922
2 51616
2 171196
2 159598
2 136432
2 84454
2 61806
2 136968
2 167442
2 150036
2 23974
2 10064
2 86342
2 146274
2 174318
2 130832
2 118838
2 180...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
99999
0 86548 1 15661
0 30345 1 15659
1 29124 1 23919
1 55755 1 23917
2 68290 1 132201
2 13438 1 132199
3 9859 1 117655
3 13368 1 117653
4 67987 1 162751
4 23781 1 162749
5 24499 1 183011
5 79051 1 183009
6 5988 1 75555
6 12841 1 75553
7 68430 1 29741
7 ...

result:

ok 

Test #10:

score: 5
Accepted
time: 9ms
memory: 6284kb

input:

ba73dbf9c7d5e5202834d6a500541c
10000
2 3124
2 3126
2 3128
2 3130
2 3132
2 3134
2 3136
2 3138
2 3140
2 3142
2 3144
2 3146
2 3148
2 3150
2 3152
2 3154
2 3156
2 3158
2 3160
2 3162
2 3164
2 3166
2 3168
2 3170
2 3172
2 3174
2 3176
2 3178
2 3180
2 3182
2 3184
2 3186
2 3188
2 3190
2 3192
2 3194
2 3196
2 31...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
9999
0 1 1 3125
1 2 1 3127
2 3 1 3129
3 4 1 3131
4 5 1 3133
5 6 1 3135
6 7 1 3137
7 8 1 3139
8 9 1 3141
9 10 1 3143
10 11 1 3145
11 12 1 3147
12 13 1 3149
13 14 1 3151
14 15 1 3153
15 16 1 3155
16 17 1 3157
17 18 1 3159
18 19 1 3161
19 20 1 3163
20 21 1 ...

result:

ok 

Test #11:

score: 5
Accepted
time: 59ms
memory: 15992kb

input:

ba73dbf9c7d5e5202834d6a500541c
53891
2 3566
2 3568
2 3570
2 3572
2 3574
2 3576
2 3578
2 3580
2 3582
2 3584
2 3586
2 3588
2 3590
2 3592
2 3594
2 3596
2 3598
2 3600
2 3602
2 3604
2 3606
2 3608
2 3610
2 3612
2 3614
2 3616
2 3618
2 3620
2 3622
2 3624
2 3626
2 3628
2 3630
2 3632
2 3634
2 3636
2 3638
2 36...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
53890
0 1 1 3567
1 2 1 3569
2 3 1 3571
3 4 1 3573
4 5 1 3575
5 6 1 3577
6 7 1 3579
7 8 1 3581
8 9 1 3583
9 10 1 3585
10 11 1 3587
11 12 1 3589
12 13 1 3591
13 14 1 3593
14 15 1 3595
15 16 1 3597
16 17 1 3599
17 18 1 3601
18 19 1 3603
19 20 1 3605
20 21 1...

result:

ok 

Test #12:

score: 5
Accepted
time: 14ms
memory: 7124kb

input:

ba73dbf9c7d5e5202834d6a500541c
14979
2 4954
2 4956
2 4958
2 4960
2 4962
2 4964
2 4966
2 4968
2 4970
2 4972
2 4974
2 4976
2 4978
2 4980
2 4982
2 4984
2 4986
2 4988
2 4990
2 4992
2 4994
2 4996
2 4998
2 5000
2 5002
2 5004
2 5006
2 5008
2 5010
2 5012
2 5014
2 5016
2 5018
2 5020
2 5022
2 5024
2 5026
2 50...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
14978
0 1 1 4955
1 2 1 4957
2 3 1 4959
3 4 1 4961
4 5 1 4963
5 6 1 4965
6 7 1 4967
7 8 1 4969
8 9 1 4971
9 10 1 4973
10 11 1 4975
11 12 1 4977
12 13 1 4979
13 14 1 4981
14 15 1 4983
15 16 1 4985
16 17 1 4987
17 18 1 4989
18 19 1 4991
19 20 1 4993
20 21 1...

result:

ok 

Test #13:

score: 5
Accepted
time: 43ms
memory: 12204kb

input:

ba73dbf9c7d5e5202834d6a500541c
44171
2 36500
2 36502
2 36504
2 36506
2 36508
2 36510
2 36512
2 36514
2 36516
2 36518
2 36520
2 36522
2 36524
2 36526
2 36528
2 36530
2 36532
2 36534
2 36536
2 36538
2 36540
2 36542
2 36544
2 36546
2 36548
2 36550
2 36552
2 36554
2 36556
2 36558
2 36560
2 36562
2 36564...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #14:

score: 5
Accepted
time: 1ms
memory: 4296kb

input:

ba73dbf9c7d5e5202834d6a500541c
1000
2 20406
2 20378
2 37840
2 37702
2 20448
2 37688
2 37780
2 20720
2 38256
2 20612
2 38050
2 20152
2 37880
2 20116
2 20030
2 20526
2 38324
2 20956
2 20852
2 20356
2 37668
2 20292
2 37648
2 20320
2 20078
2 38060
2 38014
2 37738
2 37878
2 20336
2 20472
2 20214
2 38340
...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #15:

score: 5
Accepted
time: 2ms
memory: 4204kb

input:

ba73dbf9c7d5e5202834d6a500541c
2000
2 19578
2 1754
2 1760
2 130946
2 164378
2 1038
2 20302
2 131788
2 131632
2 164392
2 19868
2 164924
2 131380
2 130972
2 131348
2 1070
2 131568
2 19492
2 19876
2 131606
2 1142
2 1588
2 1424
2 1726
2 131416
2 946
2 20158
2 19574
2 20106
2 1736
2 1186
2 19476
2 164256...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #16:

score: 5
Accepted
time: 167ms
memory: 26316kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
2 103034
2 75068
2 69976
2 84860
2 113488
2 156808
2 109250
2 119184
2 169250
2 182382
2 161594
2 169232
2 41046
2 87158
2 10192
2 32612
2 84228
2 49708
2 157912
2 160028
2 160234
2 167142
2 22010
2 37360
2 64100
2 113388
2 81460
2 52862
2 77902
2 155958
2 13330...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
99999
0 21451 1 103035
0 22204 1 103033
1 23594 1 75069
1 41977 1 75067
2 35896 1 69977
2 89253 1 69975
3 19303 1 84861
3 83859 1 84859
4 98266 1 113489
4 99175 1 113487
5 4928 1 156809
5 98562 1 156807
6 66778 1 109251
6 45395 1 109249
7 94027 1 119185
...

result:

ok 

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #17:

score: 10
Accepted
time: 0ms
memory: 3844kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
4 4
2 4
4 2
2 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
3
0 2 5 3
1 3 1 3
2 3 3 3

result:

ok 

Test #18:

score: 10
Accepted
time: 0ms
memory: 3800kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
4 4
2 6
2 4
4 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
3
0 3 3 5
0 2 3 3
1 2 1 5

result:

ok 

Test #19:

score: 10
Accepted
time: 0ms
memory: 3844kb

input:

ba73dbf9c7d5e5202834d6a500541c
6
4 6
2 4
2 2
4 2
4 4
2 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
5
0 4 3 5
1 5 1 5
1 2 1 3
2 3 3 3
3 4 5 3

result:

ok 

Test #20:

score: 10
Accepted
time: 0ms
memory: 4124kb

input:

ba73dbf9c7d5e5202834d6a500541c
8
4 2
2 6
4 8
2 4
4 6
2 2
4 4
2 8

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
7
0 6 5 3
0 5 3 3
1 7 1 7
1 3 1 5
2 4 5 7
3 5 1 3
4 6 3 5

result:

ok 

Test #21:

score: 10
Accepted
time: 0ms
memory: 4132kb

input:

ba73dbf9c7d5e5202834d6a500541c
8
2 10
2 4
4 4
4 8
2 2
2 8
4 10
4 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #22:

score: 10
Accepted
time: 0ms
memory: 3896kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
2 200000
4 199998
2 199998
4 200000

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
3
0 2 1 199999
1 3 5 199999
1 2 3 199999

result:

ok 

Test #23:

score: 10
Accepted
time: 497ms
memory: 49504kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
4 177614
4 159166
2 99950
4 127824
2 158654
4 82678
2 76278
2 198694
4 142000
4 8782
2 49352
2 71260
2 194790
2 87904
2 70702
2 20966
4 161326
2 52586
2 18108
2 36098
2 160702
2 102232
2 67042
2 16712
2 141944
4 27120
4 43282
4 139388
2 144766
4 75542
4 5228
2 1...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199999
0 59080 5 177615
0 76079 3 177613
1 116266 5 159167
1 113598 3 159165
2 187777 1 99951
2 171355 1 99949
3 83598 3 127825
3 70972 5 127823
4 185799 1 158655
4 18005 1 158653
5 109284 5 82679
5 78787 3 82677
6 41108 1 76279
6 192055 1 76277
7 9969 1...

result:

ok 

Test #24:

score: 10
Accepted
time: 0ms
memory: 3912kb

input:

ba73dbf9c7d5e5202834d6a500541c
8
2 183570
4 183570
4 183572
2 183572
2 183578
4 183574
2 183576
4 183576

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
7
0 1 3 183571
0 3 1 183571
1 2 5 183571
2 5 3 183573
4 6 1 183577
5 7 5 183575
6 7 3 183575

result:

ok 

Test #25:

score: 10
Accepted
time: 2ms
memory: 4120kb

input:

ba73dbf9c7d5e5202834d6a500541c
1173
2 186526
2 185928
4 185842
4 185780
4 185692
4 186148
4 186016
2 186236
4 185948
4 185626
2 186332
4 186206
2 186480
4 186154
2 186542
2 186504
2 186230
2 186654
2 185902
4 186762
4 186074
2 185804
4 186262
4 185834
2 186224
4 186544
4 185604
2 186300
2 186042
4 1...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
1172
0 585 1 186527
0 43 1 186525
1 798 1 185929
1 234 1 185927
2 902 5 185843
2 517 3 185841
3 563 3 185781
3 480 5 185779
4 474 3 185693
4 936 5 185691
5 670 3 186149
5 341 5 186147
6 176 3 186017
6 689 5 186015
7 844 1 186237
7 489 1 186235
8 201 3 18...

result:

ok 

Test #26:

score: 10
Accepted
time: 4ms
memory: 4396kb

input:

ba73dbf9c7d5e5202834d6a500541c
3000
2 109002
2 197108
4 198220
4 197488
4 108286
2 109006
2 197954
2 108586
4 197416
4 197132
4 197374
4 197448
4 197898
2 108330
2 197992
4 109556
2 197598
4 108114
4 109046
2 197128
2 108454
2 108892
2 108110
4 108622
4 197756
2 197924
2 109102
2 198050
2 108460
2 1...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #27:

score: 10
Accepted
time: 5ms
memory: 4636kb

input:

ba73dbf9c7d5e5202834d6a500541c
4000
2 140462
2 140478
2 140596
2 4466
2 172072
2 140272
4 64560
2 64340
4 172244
4 64230
2 57126
4 158866
2 140482
2 64878
4 159028
4 140276
2 56814
2 4364
2 64356
4 64834
4 57096
2 3922
2 172124
4 64542
2 159218
4 140762
2 172112
4 140320
4 56964
4 158988
4 140398
2 ...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #28:

score: 10
Accepted
time: 148ms
memory: 21588kb

input:

ba73dbf9c7d5e5202834d6a500541c
80000
2 77930
2 34884
4 40062
2 34158
2 6130
4 32544
2 51290
2 50478
4 70072
4 69616
2 75800
4 5656
2 4510
2 77766
2 68358
2 42792
4 52374
4 48488
2 75616
2 46682
4 45386
4 28842
2 12918
4 8206
2 20568
2 70466
2 5562
4 61202
2 65046
4 71854
4 9510
2 45910
2 14066
4 608...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
79999
0 13711 1 77931
0 23775 1 77929
1 58477 1 34885
1 33326 1 34883
2 56813 5 40063
2 55865 3 40061
3 64583 1 34159
3 52056 1 34157
4 2150 1 6131
4 47236 1 6129
5 8847 3 32545
5 13806 5 32543
6 42841 1 51291
6 46608 1 51289
7 63755 1 50479
7 21396 1 50...

result:

ok 

Test #29:

score: 10
Accepted
time: 255ms
memory: 31032kb

input:

ba73dbf9c7d5e5202834d6a500541c
120000
2 107882
4 86012
4 127996
2 176868
2 178032
4 122930
4 178436
4 160026
4 152606
2 160512
2 84884
2 161726
4 190586
2 149048
2 131608
2 80390
2 155598
4 84696
2 182976
4 158014
4 173998
2 159392
4 128890
4 119618
4 196866
2 97962
4 188404
2 133252
4 166790
4 1593...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
119999
0 30090 1 107883
0 112528 1 107881
1 109092 3 86013
1 18968 5 86011
2 44395 3 127997
2 107399 5 127995
3 9070 1 176869
3 108142 1 176867
4 79372 1 178033
4 98903 1 178031
5 62081 5 122931
5 92384 3 122929
6 108793 3 178437
6 114295 5 178435
7 7724...

result:

ok 

Test #30:

score: 10
Accepted
time: 377ms
memory: 40084kb

input:

ba73dbf9c7d5e5202834d6a500541c
160000
2 52858
4 164410
2 75528
2 52886
4 109942
4 170460
2 186328
2 124554
4 197478
2 192650
4 78512
4 153868
4 155132
2 162316
4 122256
2 166830
2 163464
2 129030
4 191906
4 68290
4 64288
4 152134
4 79376
2 125460
4 51150
2 106656
4 139088
2 136352
2 52620
4 95892
2 ...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
159999
0 30042 1 52859
0 137867 1 52857
1 103782 5 164411
1 52543 3 164409
2 65071 1 75529
2 115638 1 75527
3 67481 1 52887
3 61317 1 52885
4 64092 5 109943
4 5792 3 109941
5 24544 3 170461
5 156604 5 170459
6 127043 1 186329
6 36685 1 186327
7 69381 1 1...

result:

ok 

Test #31:

score: 10
Accepted
time: 500ms
memory: 49520kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
4 159176
4 173814
4 148140
4 192932
2 10458
4 82176
2 192792
4 58608
4 152072
2 179396
4 65044
2 43890
2 6200
4 72634
2 27580
2 178602
2 61556
4 157146
2 133400
4 126376
4 18694
2 195536
4 159494
4 84034
2 33830
4 92734
2 6522
4 109768
2 101402
4 6176
4 53030
2 ...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199999
0 40413 3 159177
0 51331 5 159175
1 88810 5 173815
1 43270 3 173813
2 18164 3 148141
2 133860 5 148139
3 62279 3 192933
3 27438 5 192931
4 132056 1 10459
4 103854 1 10457
5 95086 3 82177
5 21322 5 82175
6 179624 1 192793
6 54728 1 192791
7 193402 ...

result:

ok 

Test #32:

score: 10
Accepted
time: 0ms
memory: 3840kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
4 2
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
1
0 1 5 3

result:

ok 

Test #33:

score: 10
Accepted
time: 0ms
memory: 3828kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 2
4 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
1
0 1 3 3

result:

ok 

Test #34:

score: 10
Accepted
time: 0ms
memory: 3828kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 4
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
1
0 1 3 3

result:

ok 

Test #35:

score: 10
Accepted
time: 0ms
memory: 3784kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 2
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #36:

score: 10
Accepted
time: 0ms
memory: 3912kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 4
4 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #37:

score: 10
Accepted
time: 0ms
memory: 3852kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 2
2 4
4 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 2 3 3
0 1 1 3

result:

ok 

Test #38:

score: 10
Accepted
time: 0ms
memory: 3836kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 2
2 4
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 1 1 3
1 2 3 3

result:

ok 

Test #39:

score: 10
Accepted
time: 0ms
memory: 4132kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 2
4 2
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 1 3 3
1 2 5 3

result:

ok 

Test #40:

score: 10
Accepted
time: 0ms
memory: 3840kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 4
4 2
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 2 3 3
1 2 5 3

result:

ok 

Test #41:

score: 10
Accepted
time: 0ms
memory: 4128kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 4
4 2
4 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #42:

score: 10
Accepted
time: 0ms
memory: 4128kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 200000
2 199998
4 200000

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 2 3 199999
0 1 1 199999

result:

ok 

Test #43:

score: 10
Accepted
time: 2ms
memory: 4244kb

input:

ba73dbf9c7d5e5202834d6a500541c
2000
2 66072
2 15600
2 65278
2 65372
2 15154
2 64698
4 15472
4 15336
4 15714
4 65714
2 65516
4 65552
2 64890
2 15174
2 65674
2 14732
2 15150
4 65768
2 15672
2 14610
4 15530
2 65776
2 15370
4 65724
2 15308
2 15412
4 15712
4 14620
4 14600
2 15404
4 15918
2 14858
2 15488
...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #44:

score: 10
Accepted
time: 2ms
memory: 4708kb

input:

ba73dbf9c7d5e5202834d6a500541c
3000
2 111548
2 111040
4 70070
2 177612
2 110868
2 111368
4 17940
2 111432
2 59736
2 177494
4 110958
2 70064
2 59920
2 70092
4 177672
2 59336
4 69988
4 111040
2 59840
4 18638
4 18042
2 111192
2 177526
4 69992
4 177776
4 69676
4 177824
4 111128
4 111278
4 59162
2 111592...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #45:

score: 10
Accepted
time: 192ms
memory: 26112kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
4 169676
2 166424
4 184362
4 189372
4 92358
4 163106
4 106516
4 84160
2 80238
2 189392
4 195840
2 118396
4 94344
4 188728
2 189284
2 164532
2 140524
2 126720
4 182624
4 131538
2 172512
2 163134
2 123156
4 137156
4 168310
2 140776
4 181764
2 92658
2 124148
4 1125...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
99999
0 31285 3 169677
0 57741 5 169675
1 41190 1 166425
1 94014 1 166423
2 91610 5 184363
2 28665 3 184361
3 81923 3 189373
3 42770 3 189371
4 98269 5 92359
4 31569 3 92357
5 65441 3 163107
6 44858 3 106515
7 53483 3 84159
7 17969 5 84159
8 25969 1 8023...

result:

ok 

Test #46:

score: 10
Accepted
time: 310ms
memory: 36692kb

input:

ba73dbf9c7d5e5202834d6a500541c
145093
2 166114
2 57160
2 100318
2 183710
2 157582
4 87300
2 108292
4 26942
4 152146
4 67878
2 189520
2 105504
4 182488
4 20028
4 149088
2 27528
4 54250
2 100720
2 62956
4 60756
2 107208
4 156884
2 184558
2 79524
4 152584
4 101220
2 8320
4 149952
4 2512
4 63280
2 14975...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
145092
0 17095 3 166115
0 134467 1 166115
1 136889 1 57161
1 47951 1 57159
2 69146 3 100319
2 104958 1 100319
3 19985 1 183711
3 72445 1 183709
4 65318 3 157583
5 45891 3 87301
5 125525 5 87299
6 3953 3 108291
6 131027 1 108293
6 73031 1 108291
7 61708 3...

result:

ok 

Test #47:

score: 10
Accepted
time: 302ms
memory: 36664kb

input:

ba73dbf9c7d5e5202834d6a500541c
145075
2 155250
2 136442
2 94908
2 158406
4 57086
2 97650
4 48200
2 12782
2 185128
2 197282
4 27270
2 122262
4 66214
2 31156
2 150590
2 12294
4 1562
4 94584
2 23458
4 157278
4 33026
2 191138
4 147538
2 8652
2 108482
4 67498
4 157020
2 13190
2 30028
4 77576
4 44258
4 16...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
145074
0 63781 3 155251
0 64143 1 155251
1 40870 3 136443
1 130354 1 136443
1 115124 1 136441
2 100366 1 94909
2 75949 1 94907
3 98185 3 158407
3 7770 1 158407
4 62695 3 57087
4 109672 3 57085
5 18126 3 97651
6 31510 3 48201
6 122894 3 48199
6 25692 5 48...

result:

ok 

Subtask #3:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #48:

score: 15
Accepted
time: 0ms
memory: 3832kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
6 2
4 2
6 4
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
3
0 2 7 3
0 1 5 1
1 3 5 3

result:

ok 

Test #49:

score: 15
Accepted
time: 0ms
memory: 4120kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
6 6
4 4
6 4
4 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
3
0 2 7 5
1 2 5 5
1 3 3 5

result:

ok 

Test #50:

score: 15
Accepted
time: 0ms
memory: 3844kb

input:

ba73dbf9c7d5e5202834d6a500541c
6
6 2
2 2
6 4
2 4
4 2
4 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
5
0 2 7 3
0 4 5 1
1 4 3 3
1 3 1 3
4 5 5 3

result:

ok 

Test #51:

score: 15
Accepted
time: 0ms
memory: 4136kb

input:

ba73dbf9c7d5e5202834d6a500541c
7
6 4
4 4
2 2
4 6
4 2
2 4
6 6

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
6
0 6 7 5
0 1 5 5
1 3 3 5
1 4 5 3
2 4 3 3
2 5 1 3

result:

ok 

Test #52:

score: 15
Accepted
time: 0ms
memory: 3832kb

input:

ba73dbf9c7d5e5202834d6a500541c
8
4 2
2 2
6 8
4 6
4 8
4 4
6 6
2 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
7
0 5 5 3
0 1 3 3
1 7 1 3
2 6 7 7
3 6 5 5
3 4 5 7
3 5 3 5

result:

ok 

Test #53:

score: 15
Accepted
time: 0ms
memory: 4140kb

input:

ba73dbf9c7d5e5202834d6a500541c
7
2 4
4 4
6 2
4 2
2 6
4 6
6 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
6
0 1 3 3
0 4 1 5
1 5 3 5
1 3 5 3
2 6 7 3
2 3 5 1

result:

ok 

Test #54:

score: 15
Accepted
time: 0ms
memory: 3832kb

input:

ba73dbf9c7d5e5202834d6a500541c
8
4 2
4 8
4 6
6 2
2 6
4 4
2 8
6 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
7
0 3 5 1
0 5 5 3
1 2 5 7
2 4 3 7
2 5 3 5
3 7 7 3
4 6 1 7

result:

ok 

Test #55:

score: 15
Accepted
time: 523ms
memory: 49424kb

input:

ba73dbf9c7d5e5202834d6a500541c
199998
6 95048
2 124620
6 92330
2 87562
4 64650
2 76818
6 94884
6 106050
2 87068
2 36890
4 118972
4 58310
2 59538
6 30350
4 14668
2 71226
4 83464
6 1438
2 63320
6 130540
6 20760
2 11738
6 121604
6 69304
2 35164
4 1904
6 63076
4 116444
6 96292
2 5438
6 16630
4 14906
6 8...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199997
0 113020 7 95049
0 163883 7 95047
1 62116 1 124621
1 125307 1 124619
2 129036 7 92331
2 171345 7 92329
3 42649 1 87563
3 188372 1 87561
4 91977 5 64651
4 129714 3 64649
5 35941 1 76819
5 3274 1 76817
6 69523 7 94885
6 126994 7 94883
7 123973 7 106...

result:

ok 

Test #56:

score: 15
Accepted
time: 0ms
memory: 3868kb

input:

ba73dbf9c7d5e5202834d6a500541c
10
6 183572
4 183572
4 183574
2 183576
6 183576
4 183576
2 183578
6 183570
2 183572
4 183570

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
9
0 7 7 183571
1 2 3 183573
1 8 3 183571
1 9 5 183571
2 5 5 183575
3 5 3 183575
3 6 1 183577
4 5 5 183577
7 9 5 183569

result:

ok 

Test #57:

score: 15
Accepted
time: 3ms
memory: 4244kb

input:

ba73dbf9c7d5e5202834d6a500541c
1758
2 186528
2 185930
6 186026
4 185782
4 185694
4 186150
4 186018
2 186238
4 185950
4 185628
2 186334
6 185770
2 186482
4 186156
6 185842
6 186334
2 186232
2 186656
2 185904
4 186764
4 186076
2 185806
6 185650
4 185836
2 186226
4 186546
4 185606
2 186302
2 186044
4 1...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
1757
0 1372 1 186529
0 43 1 186527
1 798 1 185931
1 234 1 185929
2 1258 7 186027
2 1419 7 186025
3 1312 5 185783
3 480 3 185781
4 474 5 185695
4 1544 3 185693
5 670 5 186151
5 341 3 186149
6 176 5 186019
6 689 3 186017
7 844 1 186239
7 489 1 186237
8 201...

result:

ok 

Test #58:

score: 15
Accepted
time: 9ms
memory: 5100kb

input:

ba73dbf9c7d5e5202834d6a500541c
6000
4 91732
4 90280
6 89008
2 91010
6 91888
4 90450
6 90196
6 90416
4 90156
6 91718
6 88708
6 89872
2 91232
2 91566
2 90018
2 89016
4 90382
2 88900
6 91918
4 89424
4 88672
2 89576
4 90656
6 88592
2 91610
2 90672
4 89684
2 91674
2 90820
2 91412
6 90820
2 91702
2 89464
...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
5999
0 1016 3 91733
0 3588 5 91731
1 5143 3 90281
1 2234 5 90279
2 3838 7 89009
2 2217 7 89007
3 687 1 91011
3 842 1 91009
4 2258 7 91889
4 5434 7 91887
5 4830 5 90451
5 4639 3 90449
6 2078 7 90197
6 4901 7 90195
7 3589 7 90417
7 3359 7 90415
8 1325 3 90...

result:

ok 

Test #59:

score: 15
Accepted
time: 14ms
memory: 5636kb

input:

ba73dbf9c7d5e5202834d6a500541c
10000
2 85892
4 103848
4 55116
2 75724
6 178108
2 178416
6 104794
6 104736
6 54334
4 76036
4 86888
4 178912
4 86578
2 85994
6 74754
2 178168
4 103636
6 179140
4 75786
4 86246
6 85520
4 178886
6 104314
6 104818
6 74798
2 104170
4 103618
2 179026
2 178698
6 75788
2 54676...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #60:

score: 15
Accepted
time: 223ms
memory: 26276kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
6 4304
4 17988
4 43862
6 2282
6 37606
2 66400
2 11222
2 26524
2 66522
6 29288
2 54226
2 45692
4 66428
4 22820
6 65310
2 50814
2 8860
6 48664
2 40386
4 54982
2 23044
4 31694
4 6372
6 38602
2 9752
4 32596
6 53798
4 49586
2 24848
6 23096
6 40944
2 48824
6 16910
6 6...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
99999
0 28768 7 4305
0 80599 7 4303
1 63738 3 17989
1 38112 5 17987
2 9315 5 43863
2 83033 3 43861
3 25421 7 2283
3 27442 7 2281
4 62516 7 37607
4 8076 7 37605
5 39877 1 66401
5 8662 1 66399
6 23573 1 11223
6 10983 1 11221
7 64126 1 26525
7 85513 1 26523...

result:

ok 

Test #61:

score: 15
Accepted
time: 311ms
memory: 34244kb

input:

ba73dbf9c7d5e5202834d6a500541c
135000
4 80108
4 55532
6 15996
2 55940
6 40018
4 78816
6 35830
6 17658
2 86938
4 83772
2 72238
6 5506
6 61968
2 58268
6 43876
2 23076
4 27904
4 89178
6 35424
6 35176
4 89584
2 78888
6 7010
6 12638
2 42660
4 44862
6 60734
4 79580
2 74128
2 18674
2 19372
6 73860
6 54040
...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
135000
0 18121 3 80109
0 87773 5 80107
1 59075 3 55533
1 64765 5 55531
2 108121 7 15997
2 17696 7 15995
3 42620 1 55941
3 29359 1 55939
4 92831 7 40019
4 58403 7 40017
5 29040 3 78817
5 88434 5 78815
6 128874 7 35831
6 70572 7 35829
7 117251 7 17659
7 11...

result:

ok 

Test #62:

score: 15
Accepted
time: 426ms
memory: 41280kb

input:

ba73dbf9c7d5e5202834d6a500541c
165000
6 172066
4 138088
2 134464
6 123142
4 170926
2 117864
2 185690
6 179060
6 187756
6 91450
4 92788
6 97334
6 134770
6 139588
2 121126
4 136832
4 197742
6 100388
6 91908
2 109104
6 106976
2 107942
4 142116
4 115082
2 113344
6 172824
6 110544
6 112464
4 149004
6 175...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
164999
0 42834 7 172067
0 44444 7 172065
1 106559 3 138089
1 84733 5 138087
2 154410 1 134465
2 4583 1 134463
3 32309 7 123143
3 48964 7 123141
4 122524 5 170927
4 42065 3 170925
5 34084 1 117865
5 15620 1 117863
6 131313 1 185691
6 102009 1 185689
7 808...

result:

ok 

Test #63:

score: 15
Accepted
time: 504ms
memory: 49476kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
6 86562
2 132164
2 161960
4 166102
4 94656
6 164844
6 45856
2 99300
4 77424
6 76788
6 162328
4 78372
4 103764
4 140704
6 127746
4 169652
4 96084
4 49796
6 172202
6 104484
4 167568
4 176392
6 129104
4 49314
4 56440
6 102854
4 59986
6 118008
6 145490
6 74630
4 788...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
200000
0 159385 7 86563
0 65982 7 86561
1 1049 1 132165
1 147072 1 132163
2 55095 1 161961
2 50408 1 161959
3 40548 5 166103
3 90189 3 166101
4 107752 3 94657
4 187443 5 94655
5 79457 7 164845
5 187909 7 164843
6 168191 7 45857
6 65936 7 45855
7 40481 1 ...

result:

ok 

Test #64:

score: 15
Accepted
time: 0ms
memory: 3832kb

input:

ba73dbf9c7d5e5202834d6a500541c
2
2 2
6 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #65:

score: 15
Accepted
time: 0ms
memory: 3800kb

input:

ba73dbf9c7d5e5202834d6a500541c
3
2 2
4 2
6 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 1 3 3
1 2 5 1

result:

ok 

Test #66:

score: 15
Accepted
time: 0ms
memory: 3840kb

input:

ba73dbf9c7d5e5202834d6a500541c
4
2 4
4 2
4 6
6 4

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #67:

score: 15
Accepted
time: 405ms
memory: 49528kb

input:

ba73dbf9c7d5e5202834d6a500541c
199999
2 115866
2 154134
2 3960
6 59348
6 111954
6 53896
2 15912
6 199914
2 163078
6 49868
2 137758
2 48042
2 69990
2 70364
2 133946
2 34468
2 130622
2 15364
6 196702
6 46780
2 128410
6 18592
6 4278
6 133068
6 142246
6 26900
6 43072
2 122198
6 124978
2 159380
2 85902
2...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199998
0 104827 1 115867
0 186952 1 115865
1 183721 1 154135
1 55088 1 154133
2 16916 1 3961
2 34556 1 3959
3 94831 7 59349
3 147130 7 59347
4 123446 7 111955
4 2242 7 111953
5 47931 7 53897
5 49488 7 53895
6 125864 1 15913
6 48012 1 15911
7 94608 7 1999...

result:

ok 

Test #68:

score: 15
Accepted
time: 385ms
memory: 49512kb

input:

ba73dbf9c7d5e5202834d6a500541c
199999
2 90630
6 168226
6 175968
2 130260
2 126026
6 119368
6 52682
6 64202
6 70518
2 170700
2 21860
2 178410
2 76192
2 38016
6 199270
6 23782
2 192152
2 106458
2 80892
6 163314
2 106656
6 49920
6 157054
2 136682
2 55556
2 79540
2 106102
6 88696
6 7678
2 52468
2 172280...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199998
0 192623 1 90631
0 112530 1 90629
1 164262 7 168227
1 92855 7 168225
2 190806 7 175969
2 2754 7 175967
3 124555 1 130261
3 28117 1 130259
4 7478 1 126027
4 68157 1 126025
5 55464 7 119369
5 24479 7 119367
6 60456 7 52683
6 150543 7 52681
7 71666 7...

result:

ok 

Test #69:

score: 15
Accepted
time: 398ms
memory: 49256kb

input:

ba73dbf9c7d5e5202834d6a500541c
199005
6 34654
2 127948
6 190536
6 15644
2 120332
6 178698
6 3046
6 62338
6 12832
6 2824
2 48818
2 44152
6 71348
6 58418
2 151464
6 152242
2 111332
6 138662
6 146622
2 110626
6 6934
2 39908
2 108378
6 21936
6 164090
6 15418
2 36712
6 81888
6 146740
6 199770
6 158344
6 ...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199004
0 77708 7 34655
0 165853 7 34653
1 22264 1 127949
1 159609 1 127947
2 20266 7 190537
2 182570 7 190535
3 173252 7 15645
3 187467 7 15643
4 95824 1 120333
4 8401 1 120331
5 78230 7 178699
5 66681 7 178697
6 6305 7 3047
6 121384 7 3045
7 158345 7 62...

result:

ok 

Test #70:

score: 15
Accepted
time: 5ms
memory: 4628kb

input:

ba73dbf9c7d5e5202834d6a500541c
4000
6 103928
6 191558
6 192994
6 104234
6 104228
6 192602
6 191276
6 192742
6 102730
6 102798
2 102814
2 191852
4 193088
2 192554
2 191866
6 192580
2 102534
2 104064
4 102812
4 103152
4 104060
6 104430
4 192606
6 192594
6 191350
2 103266
2 191778
2 191878
6 192648
2 1...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #71:

score: 15
Accepted
time: 11ms
memory: 5240kb

input:

ba73dbf9c7d5e5202834d6a500541c
8000
6 141670
6 184016
6 5642
4 184462
4 7172
4 185262
2 127694
6 184208
2 127008
6 5812
2 141736
6 184706
2 141928
6 141792
2 6068
2 7032
6 142914
2 127674
6 184572
2 143142
2 127594
2 128398
6 5628
6 5856
4 143130
6 6290
4 184104
4 142184
6 141864
4 7106
4 127108
2 1...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #72:

score: 15
Accepted
time: 196ms
memory: 26320kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
6 42836
2 5972
2 35490
6 39484
4 28614
2 35194
2 2202
4 80528
4 30536
4 90140
6 92102
6 54632
6 34240
4 84986
4 37206
4 64602
2 43952
6 49232
4 9034
2 67488
4 54660
2 16758
4 25776
2 89570
2 39854
2 16688
2 71262
6 79192
2 46376
2 47100
4 63702
2 10200
6 30688
2...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
99999
0 60144 7 42837
1 90940 1 5973
1 71393 1 5971
2 89171 1 35491
2 80923 1 35489
3 47563 7 39485
3 59224 5 39485
4 15301 5 28613
4 13842 5 28615
4 49724 3 28613
5 51366 1 35195
5 67242 1 35193
6 93064 1 2201
7 6342 5 80529
7 92599 3 80529
7 12824 3 80...

result:

ok 

Test #73:

score: 15
Accepted
time: 315ms
memory: 37816kb

input:

ba73dbf9c7d5e5202834d6a500541c
150000
6 78236
4 79810
4 91776
2 64708
4 102410
4 70544
2 103230
6 172210
4 115452
6 112350
4 54632
4 94094
2 70820
2 136734
6 59966
6 63288
6 158212
4 183616
2 142072
6 84484
2 184338
4 197862
2 96278
6 120562
2 66086
4 97884
6 115196
2 176864
6 138738
2 173644
6 1435...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
149999
0 21421 7 78237
0 149675 7 78235
1 119289 5 79809
1 93471 3 79809
2 142985 5 91777
2 57567 3 91777
2 57001 5 91775
3 127930 3 64707
3 19153 1 64709
3 129603 1 64707
4 64292 3 102411
4 125753 3 102409
5 77678 3 70545
5 83257 5 70543
6 62555 3 10323...

result:

ok 

Test #74:

score: 15
Accepted
time: 459ms
memory: 49516kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
4 87744
2 105360
6 34704
2 171792
4 20694
6 25286
4 111544
6 25068
6 64900
2 15046
6 42920
2 56676
6 73896
6 62404
4 12270
4 170618
4 53634
2 178476
4 16464
6 188544
6 76360
4 15978
4 121632
4 38548
6 17998
2 106472
2 152492
2 70066
2 137378
4 55310
4 110092
2 9...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199999
0 169885 3 87745
0 170109 3 87743
1 162506 1 105361
1 82003 1 105359
2 142936 7 34705
2 120630 7 34703
3 152833 3 171791
4 118729 5 20693
4 150359 3 20695
5 172031 7 25287
5 1170 7 25285
6 190947 3 111545
6 98582 3 111543
6 35191 5 111543
7 69889 ...

result:

ok 

Test #75:

score: 15
Accepted
time: 503ms
memory: 53212kb

input:

ba73dbf9c7d5e5202834d6a500541c
199998
2 4288
6 133692
4 30182
2 60312
4 47290
6 120388
2 130714
6 53616
4 91442
6 58218
6 71180
2 104478
6 57206
2 86644
2 93842
4 10502
2 92832
2 136286
6 157256
4 13610
4 148186
4 43542
2 18784
4 103326
4 15658
6 60290
2 23282
6 85690
6 148178
2 59640
2 84698
2 7120...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
239996
0 180797 1 4289
0 109714 1 4287
1 125465 7 133693
1 120034 7 133691
2 102591 5 30181
2 134374 3 30183
3 107580 1 60313
3 64193 1 60311
4 118653 5 47289
4 36197 3 47291
5 13862 7 120389
5 149790 7 120387
6 190686 3 130715
6 157856 1 130715
6 37698 ...

result:

ok 

Test #76:

score: 15
Accepted
time: 425ms
memory: 49460kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
2 129082
6 72610
6 194734
2 112750
6 82944
6 30138
6 15770
6 183396
2 154782
2 193764
2 194778
2 166484
2 193426
2 188262
2 145992
2 174192
6 123650
6 7554
2 119606
6 29826
6 67290
6 85018
2 126458
6 98598
6 55728
2 19416
2 57930
6 51516
6 193690
6 149696
6 6076...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
200000
0 161571 1 129083
0 78853 1 129081
1 37743 7 72611
1 58453 7 72609
2 133530 7 194735
2 17024 7 194733
3 43080 1 112751
3 111414 1 112749
4 135342 7 82945
4 19694 7 82943
5 70430 7 30139
5 47863 7 30137
6 56170 7 15771
6 78563 7 15769
7 199243 7 18...

result:

ok 

Test #77:

score: 15
Accepted
time: 7ms
memory: 4772kb

input:

ba73dbf9c7d5e5202834d6a500541c
5000
4 156154
4 156368
2 196426
6 156928
6 196174
6 196750
4 197822
4 157596
6 197540
6 156240
6 157920
4 156878
6 158036
4 157232
4 196778
6 197648
6 198212
2 196894
2 197104
6 157446
4 158124
4 157874
4 158094
2 156192
2 157168
4 156104
6 156272
2 156800
6 156712
4 1...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #78:

score: 15
Accepted
time: 13ms
memory: 5496kb

input:

ba73dbf9c7d5e5202834d6a500541c
9000
4 170344
4 169674
2 32968
6 32518
6 169052
6 32668
6 167364
6 170438
2 113068
6 113654
6 169248
2 73998
2 113724
4 168816
6 114556
6 73758
6 169778
2 114014
4 168766
6 32746
4 33158
2 168994
6 113252
2 167962
2 74106
6 74430
2 33446
6 113268
4 167946
2 169548
6 16...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #79:

score: 15
Accepted
time: 211ms
memory: 27152kb

input:

ba73dbf9c7d5e5202834d6a500541c
100000
6 66826
6 39954
2 73296
2 75802
2 4612
4 61128
6 31252
6 31446
4 40332
2 9172
4 71820
6 84754
4 21092
6 61782
6 64606
6 51960
2 83080
2 19798
2 58636
2 87918
2 47708
4 11814
4 23664
2 50458
6 40382
2 63084
4 9814
2 72088
2 50462
4 50442
4 77972
6 1870
2 30758
2 ...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
110436
0 32806 5 66825
1 96989 7 39955
1 9334 5 39953
2 85177 1 73297
2 69353 1 73295
3 67177 1 75803
3 7522 1 75801
4 81598 1 4613
4 43214 1 4611
5 21224 5 61129
5 38649 3 61127
6 38214 7 31253
6 73549 7 31251
7 49294 7 31447
7 58305 7 31445
8 71869 5 4...

result:

ok 

Test #80:

score: 15
Accepted
time: 333ms
memory: 39468kb

input:

ba73dbf9c7d5e5202834d6a500541c
150000
2 174028
4 144676
2 118168
6 186418
4 106026
2 169150
4 190940
2 67752
2 196266
4 96144
2 124170
2 82348
4 155326
6 144152
6 108674
2 127704
6 147302
2 94080
6 88216
4 121306
6 148108
2 73550
4 122830
6 112894
6 98012
2 195176
2 82024
6 152408
2 72600
4 80088
4 ...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
165896
0 143486 1 174029
0 80107 1 174027
1 92702 5 144677
1 70474 3 144675
2 98311 3 118167
2 4805 1 118169
2 33493 1 118167
3 117070 7 186419
3 869 7 186417
4 50825 5 106025
4 23993 3 106027
5 102246 1 169151
5 6596 1 169149
6 64245 3 190941
6 45111 5 ...

result:

ok 

Test #81:

score: 15
Accepted
time: 487ms
memory: 51500kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
2 52140
2 66722
6 68358
4 184262
6 44806
6 104740
4 58058
6 25488
6 29594
4 52850
6 130906
6 55904
2 160352
6 116632
4 52134
6 137734
2 180134
2 106380
6 114282
2 194328
6 79594
6 184894
2 42778
2 102758
6 144008
6 50926
6 119278
4 128810
4 21484
2 134002
6 1561...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
221171
0 155719 3 52139
1 87612 3 66723
1 191344 1 66721
2 108500 7 68359
2 37195 5 68357
3 147699 5 184261
3 80040 3 184263
4 87051 7 44807
4 56079 7 44805
5 42061 7 104741
5 16300 7 104739
6 81932 5 58057
6 37667 5 58059
6 82807 3 58059
6 191253 3 5805...

result:

ok 

Subtask #4:

score: 0
Wrong Answer

Test #82:

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

input:

ba73dbf9c7d5e5202834d6a500541c
3
200000 2
200000 4
199998 2

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 1 200001 3
0 2 199999 3

result:

ok 

Test #83:

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

input:

ba73dbf9c7d5e5202834d6a500541c
3
200000 200000
200000 199998
199998 200000

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
2
0 2 199999 199999
0 1 200001 199999

result:

ok 

Test #84:

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

input:

ba73dbf9c7d5e5202834d6a500541c
12
2 2
2 4
4 2
2 200000
2 199998
4 200000
200000 2
200000 4
199998 2
200000 200000
200000 199998
199998 200000

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
0

result:

ok 

Test #85:

score: 20
Accepted
time: 482ms
memory: 49472kb

input:

ba73dbf9c7d5e5202834d6a500541c
199999
195232 4772
192370 7632
64282 135722
174444 25558
54846 145156
70170 129832
196228 3774
23234 176768
186862 13140
22458 177546
18158 181846
144902 55100
109692 90310
154220 45782
180406 19598
176744 23260
69098 130906
83308 116694
728 199274
143272 56730
17012 1...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199998
0 183397 195231 4771
0 114192 195233 4771
1 137403 192371 7631
1 172969 192371 7633
2 127552 64281 135721
2 183528 64283 135721
3 110702 174445 25557
3 136306 174445 25559
4 24147 54847 145155
4 81542 54847 145157
5 14273 70171 129831
5 175852 701...

result:

ok 

Test #86:

score: 0
Wrong Answer
time: 502ms
memory: 49412kb

input:

ba73dbf9c7d5e5202834d6a500541c
199997
56858 56864
1456 1462
51406 51410
89266 89272
53562 53556
80164 80158
13970 13966
41960 41966
48338 48342
98766 98772
82904 82898
38168 38172
28780 28774
38142 38146
16616 16612
15258 15262
69676 69672
85410 85416
59306 59310
712 718
6144 6140
61280 61286
28928 ...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199996
0 69117 56859 56863
0 178618 56857 56863
1 94816 1457 1461
1 164263 1455 1461
2 10313 51405 51411
2 47909 51405 51409
3 138138 89267 89271
3 181819 89265 89271
4 195085 53563 53557
4 176501 53561 53557
5 117046 80165 80159
5 90488 80163 80159
6 72...

result:

wrong answer Tree @(7, 11) appears more than once: for edges on positions 15933 and 15934

Subtask #5:

score: 0
Wrong Answer

Test #108:

score: 20
Accepted
time: 457ms
memory: 49472kb

input:

ba73dbf9c7d5e5202834d6a500541c
200000
82422 100002
100002 52498
82816 2
97624 2
100002 58032
20638 100002
100002 7646
80512 2
2 10584
28426 100002
2 83036
2 64556
47872 100002
55196 2
85350 100002
2 95376
2 23942
12488 100002
83178 2
2 9086
85598 2
100002 78820
100002 10868
98810 2
84182 100002
2 71...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
200000
0 168975 82423 100003
0 148989 82421 100001
1 117727 100001 52499
1 67645 100003 52497
2 142334 82817 1
2 150926 82815 3
3 141442 97625 1
3 164963 97623 3
4 66537 100003 58033
4 9204 100001 58031
5 10116 20639 100003
5 106842 20637 100001
6 131543...

result:

ok 

Test #109:

score: 20
Accepted
time: 458ms
memory: 49596kb

input:

ba73dbf9c7d5e5202834d6a500541c
199999
10674 50002
7228 2
31566 50002
48790 2
87212 50002
100002 76172
54282 100002
2 33136
100002 78564
50002 9882
50848 50002
50002 83692
92422 100002
100002 78880
100002 71432
50002 65586
3750 2
50002 11898
50002 17296
50002 44774
3836 2
49936 50002
50002 48536
1542...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
200000
0 113011 10675 50003
0 28598 10673 50001
1 161862 7229 1
1 28885 7227 3
2 171672 31567 50003
2 195414 31565 50001
3 185959 48791 3
3 41810 48789 1
4 38022 87213 50001
4 83724 87211 50003
5 12634 100003 76173
5 196759 100001 76171
6 127644 54283 10...

result:

ok 

Test #110:

score: 0
Wrong Answer
time: 494ms
memory: 49416kb

input:

ba73dbf9c7d5e5202834d6a500541c
199996
47612 97612
29284 20722
30860 80858
2350 52348
49558 99558
33234 83232
9050 59048
92420 57584
4174 54172
42730 92728
72144 77860
69182 19182
77286 72716
43440 6566
57918 7918
35822 85822
24864 25142
87024 37024
96744 46746
29472 79472
28650 78648
26748 76746
253...

output:

3kr2yac8xnf3ktgcoqviaw115df6rra7is6p5uix
OK
1
199996
0 98733 47613 97613
0 58294 47613 97611
1 154430 29283 20723
1 54701 29283 20721
2 102768 30861 80859
2 32658 30859 80859
3 28722 2351 52349
3 104033 2349 52349
4 71657 49559 99559
4 36906 49559 99557
5 98107 33235 83233
5 83246 33233 83233
6 1993...

result:

wrong answer Tree @(7, 49999) appears more than once: for edges on positions 61450 and 61451

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%