QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380596#1190. Twin Trees Brosthomas_li#AC ✓5ms4396kbC++175.8kb2024-04-07 06:20:152024-04-07 06:20:19

Judging History

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

  • [2024-04-07 06:20:19]
  • 评测
  • 测评结果:AC
  • 用时:5ms
  • 内存:4396kb
  • [2024-04-07 06:20:15]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int,k>
template<class A, class B> void cmx(A& x, B y){ x = max<A>(x,y); }
template<class A, class B> void cmn(A& x, B y){ x = min<A>(x,y); }
typedef pair<int,int> pii;
typedef vector<int> vi;
template<class T> struct Point3D {
	typedef Point3D P;
	typedef const P& R;
	T x,y,z;
	explicit Point3D(T x=0, T y=0, T z=0) : x(x), y(y), z(z) {}
	bool operator<(R p) const {
		return tie(x,y,z) < tie(p.x,p.y,p.z); }
	
	P operator+(R p) const { return P(x+p.x,y+p.y,z+p.z); }
	P operator-(R p) const { return P(x-p.x,y-p.y,z-p.z); }
	P operator*(T d) const { return P(x*d,y*d,z*d); }
	P operator/(T d) const { return P(x/d,y/d,z/d); }
	T dist2() const { return x*x + y*y+z*z; }
	double dist() const { return sqrt((double)dist2()); }
	T dot(R p) const { return x*p.x + y*p.y + z*p.z; }
	P cross(R p) const {
		return P(y*p.z-z*p.y,z*p.x-x*p.z,x*p.y-y*p.x);
	}
	P rotate(double angle, P axis) const {
		double s = sin(angle), c = cos(angle); P u = axis.unit();
		return u*dot(u)*(1-c) + (*this)*c-cross(u)*s;
	}
	P unit() const { return *this / (T)dist(); }
	double phi() const {return atan2(y,x); }
	double theta() const {return atan2(sqrt(x*x+y*y),z); }

};
typedef double T;
const T EPS = 1e-9;
typedef Point3D<T> P;
bool eq(T x, T y){
	return fabs(x-y) < EPS;
}
bool lt(T x, T y){
	return x+EPS < y;
}
bool lt(P a, P b){
	if(lt(a.x,b.x)) return true;
	if(eq(a.x,b.x) && lt(a.y,b.y)) return true;
	if(eq(a.x,b.x) && eq(a.y,b.y) && lt(a.z,b.z)) return true;
	return false;
}
bool eq(P a, P b){
	return eq(a.x,b.x) && eq(a.y,b.y) && eq(a.z,b.z); 
}
signed main(){
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
	/*
	P tmp{1,1,0};
	tmp = tmp.rotate(-M_PI/4,P{0,0,1});
	cout << tmp.x << " " << tmp.y << " " << tmp.z << "\n";*/
	int n; cin >> n;
	vector<vi> adj(n),bdj(n);			
	vector<pii> ela,elb;
	vector<P> a,b;
	T sum_a = 0, sum_b = 0;
	rep(i,0,n){
		int x,y,z; cin >> x >> y >> z;
		a.PB(P{x,y,z});
	}
	rep(i,1,n){
		int u,v; cin >> u >> v;
		u--; v--;
		adj[u].PB(v); adj[v].PB(u);
		ela.PB({u,v});
		sum_a += (a[u]-a[v]).dist();
	}
	rep(i,0,n){
		int x,y,z; cin >> x >> y >> z;
		b.PB(P{x,y,z});
	}
	rep(i,1,n){
		int u,v; cin >> u >> v;
		u--; v--;
		u -= n; v -= n;
		bdj[u].PB(v); bdj[v].PB(u);
		elb.PB({u,v});
		sum_b += (b[u]-b[v]).dist();
	}
	// scale b to be a
	T scale = sum_a / sum_b;
	//cerr << "scale " << scale << "\n";
	rep(i,0,n) b[i] = b[i]*scale;	
	
	auto oa = a, ob = b;

	int ans = 0;
	// match leafs
	auto go = [&](int la, int lb){
		// move nodes to origin
		{
			P pla = a[la];
			rep(i,0,n) a[i] = a[i]-pla;
		}
		{
			P plb = b[lb];
			rep(i,0,n) b[i] = b[i]-plb;
		}
		// rotate so that x = 0, y = 0
		{
			P vec = a[adj[la][0]]-a[la];
			T angx = vec.phi();
			//cerr << "angx " << angx << "\n";
			vec = vec.rotate(-angx,P{0,0,1});
			T angy = vec.theta();
			vec = vec.rotate(-angy,P{0,1,0});
			//cerr << "angy " << angx << "\n";
			//cerr << vec.x << " " << vec.y << " " << vec.z << "\n";
			rep(i,0,n){
				a[i] = a[i].rotate(-angx,P{0,0,1});
				a[i] = a[i].rotate(-angy,P{0,1,0});
			}
		}
		{
			P vec = b[bdj[lb][0]]-b[lb];
			T angx = vec.phi();
			//cerr << "angx " << angx << "\n";
			vec = vec.rotate(-angx,P{0,0,1});
			T angy = vec.theta();
			vec = vec.rotate(-angy,P{0,1,0});
			//cerr << "angy " << angx << "\n";
			//cerr << vec.x << " " << vec.y << " " << vec.z << "\n";

			rep(i,0,n){
				b[i] = b[i].rotate(-angx,P{0,0,1});
				b[i] = b[i].rotate(-angy,P{0,1,0});
			}
		}
		
		// find non colinear in a
		vector<P> goods;
		rep(i,0,n)if(fabs(a[i].x) > EPS || fabs(a[i].y) > EPS) {
			goods.PB(a[i]);	
		}
		

		// check for current a and b
		auto chk_eq = [&](){
			/*
			cerr << "as\n";
			rep(i,0,n) cout << a[i].x << " " << a[i].y << " " << a[i].z << "\n";
			cerr << "bs\n";
			rep(i,0,n) cout << b[i].x << " " << b[i].y << " " << b[i].z << "\n";*/
			bool good = 1;	
			vector<pair<P,P>> sega,segb;
			for(auto[u,v]:ela){
				sega.PB({a[u],a[v]});
				if(lt(sega.back().SD,sega.back().FS)) swap(sega.back().FS,sega.back().SD);
			}
			for(auto[u,v]:elb){
				segb.PB({b[u],b[v]});
				if(lt(segb.back().SD,segb.back().FS)) swap(segb.back().FS,segb.back().SD);
			}
			sort(all(sega),[&](auto l, auto r){
				if(lt(l.FS,r.FS) || (eq(l.FS,r.FS) && lt(l.SD,r.SD))) return true;
				return false;
					});	
			sort(all(segb),[&](auto l, auto r){
				if(lt(l.FS,r.FS) || (eq(l.FS,r.FS) && lt(l.SD,r.SD))) return true;
				return false;
					});	
			rep(i,0,n-1){
				if(!eq(sega[i].FS,segb[i].FS) || !eq(sega[i].SD,segb[i].SD)){
					good = 0;
					break;
				}
			}
			return good;
		};
		if(!sz(goods)){
			ans += chk_eq();
			return;
		}
		auto chk_rot = [&](T thet){
			//cerr << "chk " << thet << "\n";
			auto olda = a, oldb = b;
			rep(i,0,n){
				a[i] = a[i].rotate(thet,P{0,0,1});
			}
			/*
			rep(i,0,n){
				b[i] = b[i].rotate(thet,P{0,0,1});
			}*/

			bool ret = chk_eq();
			a = olda; b = oldb;
			return ret;
		};
		// try matching p0
		P p0 = goods[0];		
		//cerr << "got " << p0.x << " " << p0.y << " " << p0.z << "\n";


		rep(i,0,n) if(eq(p0.z,b[i].z) && (fabs(b[i].x) > EPS || fabs(b[i].y) > EPS)){
			// a dot b = |a||b|cos theta		
			P u = p0,v = b[i];
			u.z = v.z = 0;
			T theta = v.phi() - u.phi();
			
			if(chk_rot(theta)) ans++;
		}
	};
	int leafa = -1;
	rep(i,0,n) if(sz(adj[i]) == 1){
		leafa = i;
		break;
	}
	rep(j,0,n) if(sz(bdj[j]) == 1){
		go(leafa,j);
		a = oa; b = ob;
	}
	cout << ans << "\n";
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0 0 0
1 0 0
3 0 0
1 2
2 3
0 0 0
0 2 2
0 3 3
4 5
5 6

output:

1

result:

ok answer is '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4004kb

input:

4
1 0 0
2 0 0
2 1 0
2 -1 0
1 2
2 3
2 4
0 1 1
0 0 0
0 2 0
0 0 2
5 6
5 7
5 8

output:

2

result:

ok answer is '2'

Test #3:

score: 0
Accepted
time: 1ms
memory: 4244kb

input:

3
0 0 0
1 0 0
3 0 0
1 2
2 3
0 0 0
0 2 2
0 3 3
4 5
5 6

output:

1

result:

ok answer is '1'

Test #4:

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

input:

7
5 3 1
5 5 3
5 1 -1
7 5 3
3 5 3
7 1 -1
3 1 -1
1 2
1 3
1 4
1 5
1 6
1 7
13 23 24
10 20 30
10 20 36
10 20 24
13 23 36
7 17 36
7 17 24
8 9
9 10
9 11
9 12
9 13
9 14

output:

4

result:

ok answer is '4'

Test #5:

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

input:

7
5 3 1
5 5 3
5 1 -1
7 5 3
3 5 3
7 1 -1
3 1 -1
1 2
1 3
1 4
1 5
1 6
1 7
13 23 24
13 23 36
10 20 30
10 20 36
10 20 24
7 17 36
7 17 24
8 9
9 10
10 11
10 12
10 13
10 14

output:

0

result:

ok answer is '0'

Test #6:

score: 0
Accepted
time: 1ms
memory: 4088kb

input:

7
5 3 1
5 5 3
5 1 -1
7 5 3
3 5 3
7 1 -1
3 1 -1
1 2
1 3
1 4
1 5
1 6
1 7
13 23 24
10 20 30
10 20 36
10 20 24
13 23 37
7 17 36
7 17 24
8 9
9 10
9 11
9 12
9 13
9 14

output:

0

result:

ok answer is '0'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3976kb

input:

9
134 234 164
185 285 198
134 234 232
185 285 266
134 234 300
185 285 334
134 234 368
185 285 402
134 234 436
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
50 30 278
184 164 680
-84 -104 680
318 298 278
-218 -238 278
452 432 680
-352 -372 680
586 566 278
-486 -506 278
10 11
10 12
11 13
12 14
13 15
14 16
15 17
16 18

output:

2

result:

ok answer is '2'

Test #8:

score: 0
Accepted
time: 1ms
memory: 4096kb

input:

9
185 285 198
134 234 436
185 285 266
185 285 402
134 234 232
134 234 300
134 234 368
134 234 164
185 285 334
1 8
1 5
2 4
3 5
3 6
4 7
6 9
7 9
318 298 278
452 432 680
184 164 680
-218 -238 278
-352 -372 680
586 566 278
-486 -506 278
-84 -104 680
50 30 278
10 12
10 11
11 15
12 18
13 17
13 14
14 16
17 18

output:

2

result:

ok answer is '2'

Test #9:

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

input:

9
185 285 198
134 234 436
185 285 266
185 285 402
134 234 232
134 234 300
134 234 368
134 234 164
185 285 334
1 8
1 5
2 6
3 5
3 6
4 7
6 9
7 9
318 298 278
452 432 680
184 164 680
-218 -238 278
-352 -372 680
586 566 278
-486 -506 278
-84 -104 680
50 30 278
10 12
10 11
11 15
12 18
13 17
13 14
14 16
17 18

output:

0

result:

ok answer is '0'

Test #10:

score: 0
Accepted
time: 1ms
memory: 4032kb

input:

9
185 285 198
134 235 436
185 285 266
185 285 402
134 234 232
134 234 300
134 234 368
134 234 164
185 285 334
1 8
1 5
2 4
3 5
3 6
4 7
6 9
7 9
318 298 278
452 432 680
184 164 680
-218 -238 278
-352 -372 680
586 566 278
-486 -506 278
-84 -104 680
50 30 278
10 12
10 11
11 15
12 18
13 17
13 14
14 16
17 18

output:

0

result:

ok answer is '0'

Test #11:

score: 0
Accepted
time: 1ms
memory: 4096kb

input:

7
-220 520 720
60 240 440
200 100 300
620 -320 -120
-80 380 580
480 -180 20
340 -40 160
1 3
1 7
1 6
1 4
2 3
3 5
230 210 370
50 30 10
170 150 250
-10 -30 -110
-130 -150 -350
110 90 130
-70 -90 -230
8 11
8 9
8 14
8 12
9 10
9 13

output:

1

result:

ok answer is '1'

Test #12:

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

input:

7
-220 520 720
60 240 440
200 100 300
620 -320 -120
-80 380 580
480 -180 20
340 -40 160
1 3
1 7
1 6
2 3
3 5
4 5
230 210 370
50 30 10
170 150 250
-10 -30 -110
-130 -150 -350
110 90 130
-70 -90 -230
8 11
8 9
8 14
8 12
9 10
9 13

output:

0

result:

ok answer is '0'

Test #13:

score: 0
Accepted
time: 1ms
memory: 4220kb

input:

7
-220 520 720
60 240 440
200 100 300
620 -320 -120
-80 380 580
480 -180 20
341 -40 161
1 3
1 7
1 6
1 4
2 3
3 5
230 210 370
50 30 10
170 150 250
-10 -30 -110
-130 -150 -350
110 90 130
-70 -90 -230
8 11
8 9
8 14
8 12
9 10
9 13

output:

0

result:

ok answer is '0'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4224kb

input:

12
-356 -256 92
-356 -256 -12
-356 -256 612
-252 -152 612
-252 -152 508
-252 -152 92
-356 -256 508
-252 -152 196
-252 -152 -12
-252 -152 404
-356 -256 404
-356 -256 196
1 4
2 4
3 11
4 5
4 12
5 11
6 12
7 11
8 12
9 12
10 11
602 582 194
234 214 562
418 398 562
-134 -154 562
234 214 194
-134 -154 194
-3...

output:

1

result:

ok answer is '1'

Test #15:

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

input:

12
-356 -256 92
-356 -256 -12
-356 -256 612
-252 -152 612
-252 -152 508
-252 -152 92
-356 -256 508
-252 -152 196
-252 -152 -12
-252 -152 404
-356 -256 404
-356 -256 196
1 4
2 4
3 11
4 5
4 12
5 11
6 7
7 11
8 12
9 12
10 11
602 582 194
234 214 562
418 398 562
-134 -154 562
234 214 194
-134 -154 194
-31...

output:

0

result:

ok answer is '0'

Test #16:

score: 0
Accepted
time: 1ms
memory: 4004kb

input:

12
-356 -256 92
-356 -256 -12
-356 -256 612
-252 -152 612
-252 -152 508
-252 -152 93
-356 -256 508
-252 -152 196
-252 -152 -12
-252 -152 404
-356 -256 404
-356 -256 196
1 4
2 4
3 11
4 5
4 12
5 11
6 12
7 11
8 12
9 12
10 11
418 398 562
-502 -522 562
-134 -154 194
234 214 562
-502 -522 194
602 582 562
...

output:

0

result:

ok answer is '0'

Test #17:

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

input:

4
-500 -400 360
-500 -400 240
100 200 240
100 200 360
1 2
2 4
3 4
890 114 94
-790 114 94
890 -54 -74
-790 -54 -74
5 8
5 7
6 8

output:

2

result:

ok answer is '2'

Test #18:

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

input:

4
-500 -400 360
-500 -400 240
100 200 240
100 200 360
1 2
2 4
3 4
890 114 94
890 -54 -74
-790 114 94
-790 -54 -74
5 8
6 7
7 8

output:

0

result:

ok answer is '0'

Test #19:

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

input:

4
-500 -400 360
-500 -400 240
100 200 240
100 200 360
1 2
2 4
3 4
-790 114 94
890 -54 -75
890 114 94
-790 -54 -74
5 8
6 7
7 8

output:

0

result:

ok answer is '0'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3972kb

input:

4
1 0 0
2 0 0
2 1 0
2 -1 0
1 2
2 3
2 4
0 1 1
0 0 0
0 2 0
0 0 2
5 6
5 7
5 8

output:

2

result:

ok answer is '2'

Test #21:

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

input:

199
-175 -10 195
-95 -125 390
-110 25 310
-105 -170 360
-145 -60 205
-340 -75 315
-305 -10 275
-245 -5 230
-175 5 390
-295 -40 230
-235 -90 205
-290 -225 310
-130 -5 360
-105 -45 260
-95 -190 275
-105 -30 345
-240 -5 355
-90 -15 365
-295 -155 260
-285 -165 410
-245 -195 370
-225 -115 160
-235 -195 2...

output:

24

result:

ok answer is '24'

Test #22:

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

input:

199
-175 -10 195
-95 -125 390
-110 25 310
-105 -170 360
-145 -60 205
-340 -75 315
-305 -10 275
-245 -5 230
-175 5 390
-295 -40 230
-235 -90 205
-290 -225 310
-130 -5 360
-105 -45 260
-95 -190 275
-105 -30 345
-240 -5 355
-90 -15 365
-295 -155 260
-285 -165 410
-245 -195 370
-225 -115 160
-235 -195 2...

output:

0

result:

ok answer is '0'

Test #23:

score: 0
Accepted
time: 1ms
memory: 4220kb

input:

199
-175 -10 195
-95 -125 390
-110 25 310
-105 -170 360
-145 -60 205
-340 -75 315
-305 -10 275
-245 -5 230
-175 5 390
-295 -40 230
-235 -90 205
-290 -225 310
-130 -5 360
-105 -45 260
-95 -190 275
-105 -30 345
-240 -5 355
-90 -15 365
-295 -155 260
-285 -165 410
-245 -195 370
-225 -115 160
-235 -195 2...

output:

0

result:

ok answer is '0'

Test #24:

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

input:

165
-170 -94 357
-221 -121 384
-191 -55 294
-143 -139 309
-158 -106 351
-161 -184 267
-146 -178 282
-209 -43 339
-158 -181 264
-149 -157 285
-179 -184 321
-215 -151 357
-209 -55 306
-239 -16 267
-185 -43 249
-221 -16 321
-209 -145 294
-233 -16 339
-248 -148 213
-194 -70 243
-242 -19 264
-179 -16 279...

output:

8

result:

ok answer is '8'

Test #25:

score: 0
Accepted
time: 1ms
memory: 4152kb

input:

165
-170 -94 357
-221 -121 384
-191 -55 294
-143 -139 309
-158 -106 351
-161 -184 267
-146 -178 282
-209 -43 339
-158 -181 264
-149 -157 285
-179 -184 321
-215 -151 357
-209 -55 306
-239 -16 267
-185 -43 249
-221 -16 321
-209 -145 294
-233 -16 339
-248 -148 213
-194 -70 243
-242 -19 264
-179 -16 279...

output:

0

result:

ok answer is '0'

Test #26:

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

input:

165
-170 -94 357
-221 -121 384
-191 -55 294
-143 -139 309
-158 -106 351
-161 -184 267
-146 -178 282
-209 -43 339
-158 -181 264
-149 -157 285
-179 -184 321
-215 -151 357
-209 -55 306
-239 -16 267
-185 -43 249
-221 -16 321
-209 -145 294
-233 -16 339
-248 -148 213
-194 -70 243
-242 -19 264
-179 -16 279...

output:

0

result:

ok answer is '0'

Test #27:

score: 0
Accepted
time: 1ms
memory: 4352kb

input:

165
-248 -58 384
-221 -139 261
-239 -121 261
-116 -58 348
-239 -88 234
-239 -106 345
-125 -151 279
-230 -121 339
-146 -55 285
-149 -109 249
-221 -61 339
-179 -49 225
-239 -115 333
-254 -85 255
-239 -133 285
-284 -148 258
-167 -115 339
-251 -49 291
-170 -121 261
-248 -142 216
-245 -94 339
-266 -112 2...

output:

4

result:

ok answer is '4'

Test #28:

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

input:

165
-248 -58 384
-221 -139 261
-239 -121 261
-116 -58 348
-239 -88 234
-239 -106 345
-125 -151 279
-230 -121 339
-146 -55 285
-149 -109 249
-221 -61 339
-179 -49 225
-239 -115 333
-254 -85 255
-239 -133 285
-284 -148 258
-167 -115 339
-251 -49 291
-170 -121 261
-248 -142 216
-245 -94 339
-266 -112 2...

output:

0

result:

ok answer is '0'

Test #29:

score: 0
Accepted
time: 1ms
memory: 4036kb

input:

165
-248 -58 384
-221 -139 261
-239 -121 261
-116 -58 348
-239 -88 234
-239 -106 345
-125 -151 279
-230 -121 339
-146 -55 285
-149 -109 249
-221 -61 339
-179 -49 225
-239 -115 333
-254 -85 255
-239 -133 285
-284 -148 258
-167 -115 339
-251 -49 291
-170 -121 261
-248 -142 216
-245 -94 339
-266 -112 2...

output:

0

result:

ok answer is '0'

Test #30:

score: 0
Accepted
time: 1ms
memory: 4056kb

input:

67
-39 -16 321
-277 -142 307
-39 -121 384
-396 -30 405
-312 -219 272
-4 -30 195
-361 -16 279
-270 -100 300
-305 5 328
-95 5 272
-361 -121 216
-95 -128 195
-88 19 272
-396 -170 195
-116 -184 412
-361 -79 384
-88 -79 384
-95 -72 405
-116 -16 188
-130 -100 300
-361 -184 321
-312 19 328
-312 -184 279
-4...

output:

8

result:

ok answer is '8'

Test #31:

score: 0
Accepted
time: 1ms
memory: 4180kb

input:

67
-39 -16 321
-277 -142 307
-39 -121 384
-396 -30 405
-312 -219 272
-4 -30 195
-361 -16 279
-270 -100 300
-305 5 328
-95 5 272
-361 -121 216
-95 -128 195
-88 19 272
-396 -170 195
-116 -184 412
-361 -79 384
-88 -79 384
-95 -72 405
-116 -16 188
-130 -100 300
-361 -184 321
-312 19 328
-312 -184 279
-4...

output:

0

result:

ok answer is '0'

Test #32:

score: 0
Accepted
time: 1ms
memory: 4116kb

input:

67
-39 -16 321
-277 -142 307
-39 -121 384
-396 -30 405
-312 -219 272
-4 -30 195
-361 -16 279
-270 -100 300
-305 5 328
-95 5 272
-361 -121 216
-95 -128 195
-88 19 272
-396 -170 195
-116 -184 412
-361 -79 384
-88 -79 384
-95 -72 405
-116 -16 188
-130 -100 300
-361 -184 321
-312 19 328
-312 -184 279
-4...

output:

0

result:

ok answer is '0'

Test #33:

score: 0
Accepted
time: 1ms
memory: 4084kb

input:

83
-81 -51 125
-242 -191 181
-123 -128 391
-109 -219 125
-326 -198 503
-81 -191 475
-277 -79 146
-144 26 426
-291 -142 419
-109 -58 419
-165 -191 97
-109 -135 503
-123 -121 146
-81 -149 475
-277 -121 454
-193 -135 216
-81 -9 125
-193 -65 384
-249 19 125
-109 -65 97
-291 -219 475
-235 -191 503
-123 -...

output:

2

result:

ok answer is '2'

Test #34:

score: 0
Accepted
time: 1ms
memory: 4004kb

input:

83
-81 -51 125
-242 -191 181
-123 -128 391
-109 -219 125
-326 -198 503
-81 -191 475
-277 -79 146
-144 26 426
-291 -142 419
-109 -58 419
-165 -191 97
-109 -135 503
-123 -121 146
-81 -149 475
-277 -121 454
-193 -135 216
-81 -9 125
-193 -65 384
-249 19 125
-109 -65 97
-291 -219 475
-235 -191 503
-123 -...

output:

0

result:

ok answer is '0'

Test #35:

score: 0
Accepted
time: 1ms
memory: 4260kb

input:

83
-81 -51 125
-242 -191 181
-123 -128 391
-109 -219 125
-326 -198 503
-81 -191 475
-277 -79 146
-144 26 426
-291 -142 419
-109 -58 419
-165 -191 97
-109 -135 503
-123 -121 146
-81 -149 475
-277 -121 454
-193 -135 216
-81 -9 125
-193 -65 384
-249 19 125
-109 -65 97
-291 -219 475
-235 -191 503
-123 -...

output:

0

result:

ok answer is '0'

Test #36:

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

input:

83
-102 -142 321
-81 -156 167
-298 -142 279
-102 -163 174
3 -65 174
-326 -44 195
-123 -198 216
-291 19 286
-109 -114 419
-81 33 244
3 -226 265
-354 -16 265
-123 -2 384
-403 -135 174
-277 -16 398
-74 -156 195
3 26 335
-319 -233 244
-277 -198 384
-81 -44 433
-102 26 237
-74 -205 356
-46 -121 321
-291 ...

output:

2

result:

ok answer is '2'

Test #37:

score: 0
Accepted
time: 1ms
memory: 3964kb

input:

83
-102 -142 321
-81 -156 167
-298 -142 279
-102 -163 174
3 -65 174
-326 -44 195
-123 -198 216
-291 19 286
-109 -114 419
-81 33 244
3 -226 265
-354 -16 265
-123 -2 384
-403 -135 174
-277 -16 398
-74 -156 195
3 26 335
-319 -233 244
-277 -198 384
-81 -44 433
-102 26 237
-74 -205 356
-46 -121 321
-291 ...

output:

0

result:

ok answer is '0'

Test #38:

score: 0
Accepted
time: 1ms
memory: 4184kb

input:

83
-102 -142 321
-81 -156 167
-298 -142 279
-102 -163 174
3 -65 174
-326 -44 195
-123 -198 216
-291 19 286
-109 -114 419
-81 33 244
3 -226 265
-354 -16 265
-123 -2 384
-403 -135 174
-277 -16 398
-74 -156 195
3 26 335
-319 -233 244
-277 -198 384
-81 -44 433
-102 26 237
-74 -205 356
-46 -121 321
-291 ...

output:

0

result:

ok answer is '0'

Test #39:

score: 0
Accepted
time: 1ms
memory: 4024kb

input:

83
-92 50 106
-4 82 -34
96 -70 66
92 -82 -14
56 50 102
40 -26 82
-8 66 10
24 -70 98
44 82 46
92 62 74
52 50 -46
24 58 90
-40 66 18
52 -70 -22
-64 102 -42
32 50 14
-80 62 82
24 -78 -30
56 10 18
-84 82 14
40 42 46
32 62 90
24 102 102
-52 98 -22
48 14 102
40 62 -22
-4 50 82
16 106 -30
-88 34 90
20 -10 ...

output:

2

result:

ok answer is '2'

Test #40:

score: 0
Accepted
time: 1ms
memory: 4328kb

input:

83
-92 50 106
-4 82 -34
96 -70 66
92 -82 -14
56 50 102
40 -26 82
-8 66 10
24 -70 98
44 82 46
92 62 74
52 50 -46
24 58 90
-40 66 18
52 -70 -22
-64 102 -42
32 50 14
-80 62 82
24 -78 -30
56 10 18
-84 82 14
40 42 46
32 62 90
24 102 102
-52 98 -22
48 14 102
40 62 -22
-4 50 82
16 106 -30
-88 34 90
20 -10 ...

output:

0

result:

ok answer is '0'

Test #41:

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

input:

83
-92 50 106
-4 82 -34
96 -70 66
92 -82 -14
56 50 102
40 -26 82
-8 66 10
24 -70 98
44 82 46
92 62 74
52 50 -46
24 58 90
-40 66 18
52 -70 -22
-64 102 -42
32 50 14
-80 62 82
24 -78 -30
56 10 18
-84 82 14
40 42 46
32 62 90
24 102 102
-52 98 -22
48 14 102
40 62 -22
-4 50 82
16 106 -30
-88 34 90
20 -10 ...

output:

0

result:

ok answer is '0'

Test #42:

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

input:

200
139 5 8
-17 5 8
231 5 8
135 5 8
-201 5 8
-377 5 8
79 5 8
123 5 8
235 5 8
-57 5 8
-225 5 8
-361 5 8
-161 5 8
-373 5 8
-129 5 8
23 5 8
-177 5 8
-65 5 8
-77 5 8
-353 5 8
267 5 8
-69 5 8
147 5 8
227 5 8
351 5 8
-305 5 8
-1 5 8
-165 5 8
55 5 8
-257 5 8
263 5 8
-121 5 8
-221 5 8
-249 5 8
159 5 8
67 5 ...

output:

1

result:

ok answer is '1'

Test #43:

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

input:

200
139 5 8
-17 5 8
231 5 8
135 5 8
-201 5 8
-377 5 8
79 5 8
123 5 8
235 5 8
-57 5 8
-225 5 8
-361 5 8
-161 5 8
-373 5 8
-129 5 8
23 5 8
-177 5 8
-65 5 8
-77 5 8
-353 5 8
267 5 8
-69 5 8
147 5 8
227 5 8
351 5 8
-305 5 8
-1 5 8
-165 5 8
55 5 8
-257 5 8
263 5 8
-121 5 8
-221 5 8
-249 5 8
159 5 8
67 5 ...

output:

0

result:

ok answer is '0'

Test #44:

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

input:

200
139 5 8
-17 5 8
231 5 8
135 5 8
-201 5 8
-377 5 8
79 5 8
123 5 8
235 5 8
-57 5 8
-225 5 8
-361 5 8
-161 5 8
-373 5 8
-129 5 8
23 5 8
-177 5 8
-65 5 8
-77 5 8
-353 5 8
267 5 8
-69 5 8
147 5 8
227 5 8
351 5 8
-305 5 8
-1 5 8
-165 5 8
55 5 8
-257 5 8
263 5 8
-121 5 8
-221 5 8
-249 5 8
159 5 8
67 5 ...

output:

0

result:

ok answer is '0'

Test #45:

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

input:

200
105 73 42
-12 -5 3
174 119 65
102 71 41
-150 -97 -43
-282 -185 -87
60 43 27
93 65 38
177 121 66
-42 -25 -7
-168 -109 -49
-270 -177 -83
-120 -77 -33
-279 -183 -86
-96 -61 -25
18 15 13
-132 -85 -37
-48 -29 -9
-57 -35 -12
-264 -173 -81
201 137 74
-51 -31 -10
111 77 44
171 117 64
264 179 95
-228 -14...

output:

1

result:

ok answer is '1'

Test #46:

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

input:

200
105 73 42
-12 -5 3
174 119 65
102 71 41
-150 -97 -43
-282 -185 -87
60 43 27
93 65 38
177 121 66
-42 -25 -7
-168 -109 -49
-270 -177 -83
-120 -77 -33
-279 -183 -86
-96 -61 -25
18 15 13
-132 -85 -37
-48 -29 -9
-57 -35 -12
-264 -173 -81
201 137 74
-51 -31 -10
111 77 44
171 117 64
264 179 95
-228 -14...

output:

0

result:

ok answer is '0'

Test #47:

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

input:

200
105 73 42
-12 -5 3
174 119 65
102 71 41
-150 -97 -43
-282 -185 -87
60 43 27
93 65 38
177 121 66
-42 -25 -7
-168 -109 -49
-270 -177 -83
-120 -77 -33
-279 -183 -86
-96 -61 -25
18 15 13
-132 -85 -37
-48 -29 -9
-57 -35 -12
-264 -173 -81
201 137 74
-51 -31 -10
111 77 44
171 117 64
264 179 95
-228 -14...

output:

0

result:

ok answer is '0'

Test #48:

score: 0
Accepted
time: 1ms
memory: 4272kb

input:

200
-473 -322 -77
-13 618 479
-49 670 -221
85 -450 477
11 -136 39
49 48 -537
-687 14 -155
-289 176 399
213 -268 -263
19 2 -19
-23 -484 -137
451 -194 281
-509 264 -195
205 -48 571
-407 -310 -311
435 -354 -267
303 188 211
309 418 327
19 -366 541
-97 276 619
291 -240 -531
-583 248 -387
339 272 481
-145...

output:

1

result:

ok answer is '1'

Test #49:

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

input:

200
-473 -322 -77
463 -444 545
-49 670 -221
85 -450 477
-653 206 -343
49 48 -537
-303 -368 525
-289 176 399
213 -268 -263
19 2 -19
-23 -484 -137
451 -194 281
-509 264 -195
205 -48 571
-407 -310 -311
225 292 -483
-157 -446 139
481 -272 527
19 -366 541
-97 276 619
291 -240 -531
-583 248 -387
339 272 4...

output:

0

result:

ok answer is '0'

Test #50:

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

input:

200
-473 -322 -77
-13 618 479
-49 670 -221
85 -450 477
11 -136 39
49 48 -537
-687 14 -155
-289 176 399
213 -268 -263
19 2 -19
-23 -484 -137
451 -194 281
-509 264 -195
205 -48 571
-407 -310 -311
435 -354 -267
303 188 211
309 418 327
19 -366 541
-97 276 619
291 -240 -531
-583 248 -387
339 272 481
-145...

output:

0

result:

ok answer is '0'

Test #51:

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

input:

200
387 5 8
35 5 8
-73 5 8
-353 5 8
-261 5 8
-61 5 8
-125 5 8
211 5 8
127 5 8
-237 5 8
99 5 8
-209 5 8
255 5 8
-137 5 8
347 5 8
-213 5 8
-97 5 8
187 5 8
-105 5 8
3 5 8
-113 5 8
-89 5 8
215 5 8
-249 5 8
243 5 8
-129 5 8
-93 5 8
319 5 8
-221 5 8
-201 5 8
-225 5 8
139 5 8
19 5 8
-1 5 8
-277 5 8
363 5 8...

output:

1

result:

ok answer is '1'

Test #52:

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

input:

200
387 5 8
35 5 8
-73 5 8
-353 5 8
-261 5 8
-61 5 8
-125 5 8
211 5 8
127 5 8
-237 5 8
99 5 8
-209 5 8
255 5 8
-137 5 8
347 5 8
-213 5 8
-97 5 8
187 5 8
-105 5 8
3 5 8
-113 5 8
-89 5 8
215 5 8
-249 5 8
243 5 8
-129 5 8
-93 5 8
319 5 8
-221 5 8
-201 5 8
-225 5 8
139 5 8
19 5 8
-1 5 8
-277 5 8
363 5 8...

output:

0

result:

ok answer is '0'

Test #53:

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

input:

200
387 5 8
35 5 8
-73 5 8
-353 5 8
-261 5 8
-61 5 8
-125 5 8
211 5 8
127 5 8
-237 5 8
99 5 8
-209 5 8
255 5 8
-137 5 8
347 5 8
-213 5 8
-97 5 8
187 5 8
-105 5 8
3 5 8
-113 5 8
-89 5 8
215 5 8
-249 5 8
243 5 8
-129 5 8
-93 5 8
319 5 8
-221 5 8
-201 5 8
-225 5 8
139 5 8
19 5 8
-1 5 8
-277 5 8
363 5 8...

output:

0

result:

ok answer is '0'

Test #54:

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

input:

200
291 197 104
27 21 16
-54 -33 -11
-264 -173 -81
-195 -127 -58
-45 -27 -8
-93 -59 -24
159 109 60
96 67 39
-177 -115 -52
75 53 32
-156 -101 -45
192 131 71
-102 -65 -27
261 177 94
-159 -103 -46
-72 -45 -17
141 97 54
-78 -49 -19
3 5 8
-84 -53 -21
-66 -41 -15
162 111 61
-186 -121 -55
183 125 68
-96 -6...

output:

1

result:

ok answer is '1'

Test #55:

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

input:

200
291 197 104
27 21 16
-54 -33 -11
-264 -173 -81
-195 -127 -58
-45 -27 -8
-93 -59 -24
159 109 60
96 67 39
-177 -115 -52
75 53 32
-156 -101 -45
192 131 71
-102 -65 -27
261 177 94
-159 -103 -46
-72 -45 -17
141 97 54
-78 -49 -19
3 5 8
-84 -53 -21
-66 -41 -15
162 111 61
-186 -121 -55
183 125 68
-96 -6...

output:

0

result:

ok answer is '0'

Test #56:

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

input:

200
291 197 104
27 21 16
-54 -33 -11
-264 -173 -81
-195 -127 -58
-45 -27 -8
-93 -59 -24
159 109 60
96 67 39
-177 -115 -52
75 53 32
-156 -101 -45
192 131 71
-102 -65 -27
261 177 94
-159 -103 -46
-72 -45 -17
141 97 54
-78 -49 -19
3 5 8
-84 -53 -21
-66 -41 -15
162 111 61
-186 -121 -55
183 125 68
-96 -6...

output:

0

result:

ok answer is '0'

Test #57:

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

input:

4
1 0 0
2 0 0
2 1 0
2 -1 0
1 2
1 3
2 4
0 1 1
0 0 0
0 2 0
0 0 2
5 6
5 7
5 8

output:

0

result:

ok answer is '0'

Test #58:

score: 0
Accepted
time: 1ms
memory: 4176kb

input:

200
-200 -520 192
-216 -610 -266
-428 46 -248
30 92 -36
-558 -534 332
138 -42 -412
240 286 46
-196 -140 -32
408 -120 -544
-236 -434 24
534 276 596
-432 -68 -406
80 -294 442
160 174 -176
330 188 180
472 -390 -352
574 422 224
292 -264 -360
-156 340 -384
498 -156 580
500 354 -494
444 -32 540
-102 298 1...

output:

1

result:

ok answer is '1'

Test #59:

score: 0
Accepted
time: 1ms
memory: 4228kb

input:

200
-380 -610 462
-396 -700 4
-608 -44 22
-150 2 234
-738 -624 602
-42 -132 -142
60 196 316
-376 -230 238
228 -210 -274
-416 -524 294
354 186 866
-612 -158 -136
-100 -384 712
-20 84 94
150 98 450
292 -480 -82
394 332 494
112 -354 -90
-336 250 -114
318 -246 850
320 264 -224
264 -122 810
-282 208 286
...

output:

0

result:

ok answer is '0'

Test #60:

score: 0
Accepted
time: 1ms
memory: 4228kb

input:

200
-380 -610 462
-396 -700 4
-608 -44 22
-150 2 234
-738 -624 602
-42 -132 -142
60 196 316
-376 -230 238
228 -210 -274
-416 -524 294
354 186 866
-612 -158 -136
-100 -384 712
-20 84 94
150 98 450
292 -480 -82
394 332 494
112 -354 -90
-336 250 -114
318 -246 850
320 264 -224
264 -122 810
-282 208 286
...

output:

0

result:

ok answer is '0'

Test #61:

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

input:

200
-917 -637 399
574 -697 354
-614 626 807
556 866 -117
418 -775 852
439 122 -45
-644 512 150
658 -706 -816
97 -844 768
433 -784 -285
-14 620 486
649 -553 -159
499 482 546
-668 -46 -570
754 398 891
607 68 30
781 815 39
-515 -184 -417
118 -586 801
427 119 -153
37 482 297
-476 -190 -504
178 791 468
-...

output:

1

result:

ok answer is '1'

Test #62:

score: 0
Accepted
time: 1ms
memory: 4304kb

input:

200
-917 -637 399
574 -697 354
-614 626 807
556 866 -117
418 -775 852
439 122 -45
-644 512 150
658 -706 -816
97 -844 768
433 -784 -285
-14 620 486
649 -553 -159
499 482 546
-668 -46 -570
754 398 891
607 68 30
781 815 39
-515 -184 -417
118 -586 801
427 119 -153
37 482 297
-476 -190 -504
178 791 468
-...

output:

0

result:

ok answer is '0'

Test #63:

score: 0
Accepted
time: 1ms
memory: 4104kb

input:

200
-917 -637 399
574 -697 354
-614 626 807
556 866 -117
418 -775 852
439 122 -45
-644 512 150
658 -706 -816
97 -844 768
433 -784 -285
-14 620 486
649 -553 -159
499 482 546
-668 -46 -570
754 398 891
607 68 30
781 815 39
-515 -184 -417
118 -586 801
427 119 -153
37 482 297
-476 -190 -504
178 791 468
-...

output:

0

result:

ok answer is '0'

Test #64:

score: 0
Accepted
time: 1ms
memory: 4176kb

input:

200
160 -268 -288
28 588 548
180 -600 296
6 340 -66
10 56 -322
618 -372 130
-566 -38 -510
40 -498 -2
-336 -412 188
-548 -286 -550
-20 -110 -98
6 318 180
-372 276 -114
392 -98 402
602 272 -30
268 -12 542
-210 -322 374
270 -558 244
-28 202 562
148 -458 494
-420 -42 188
-236 -278 -160
-110 -424 418
514...

output:

1

result:

ok answer is '1'

Test #65:

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

input:

200
160 -268 -288
28 588 548
180 -600 296
6 340 -66
10 56 -322
618 -372 130
-566 -38 -510
40 -498 -2
-336 -412 188
-548 -286 -550
-20 -110 -98
6 318 180
-372 276 -114
392 -98 402
602 272 -30
268 -12 542
-210 -322 374
270 -558 244
-28 202 562
148 -458 494
-420 -42 188
-236 -278 -160
-110 -424 418
514...

output:

0

result:

ok answer is '0'

Test #66:

score: 0
Accepted
time: 1ms
memory: 4372kb

input:

200
160 -268 -288
28 588 548
180 -600 296
6 340 -66
10 56 -322
618 -372 130
-566 -38 -510
40 -498 -2
-336 -412 188
-548 -286 -550
-20 -110 -98
6 318 180
-372 276 -114
392 -98 402
602 272 -30
268 -12 542
-210 -322 374
270 -558 244
-28 202 562
148 -458 494
-420 -42 188
-236 -278 -160
-110 -424 418
514...

output:

0

result:

ok answer is '0'

Test #67:

score: 0
Accepted
time: 1ms
memory: 4344kb

input:

200
61 112 145
55 -98 176
235 -88 126
5 -5 -12
-251 34 75
51 -254 196
158 304 286
151 -268 152
-38 302 10
-32 148 131
205 140 -92
-161 13 -215
-199 -181 -255
-300 -118 3
93 136 -88
173 222 17
-164 95 -128
-192 -107 -264
136 -190 -27
-164 -29 -95
-115 -59 -245
-82 -184 136
-228 297 59
-169 -103 -86
-...

output:

1

result:

ok answer is '1'

Test #68:

score: 0
Accepted
time: 1ms
memory: 4148kb

input:

200
61 112 145
55 -98 176
235 -88 126
5 -5 -12
-251 34 75
51 -254 196
158 304 286
151 -268 152
-38 302 10
-32 148 131
205 140 -92
-161 13 -215
-199 -181 -255
-300 -118 3
93 136 -88
173 222 17
-164 95 -128
-192 -107 -264
136 -190 -27
-164 -29 -95
-115 -59 -245
-82 -184 136
-228 297 59
-169 -103 -86
-...

output:

0

result:

ok answer is '0'

Test #69:

score: 0
Accepted
time: 1ms
memory: 4168kb

input:

200
61 112 145
55 -98 176
235 -88 126
5 -5 -12
-251 34 75
51 -254 196
158 304 286
151 -268 152
-38 302 10
-32 148 131
205 140 -92
-161 13 -215
-199 -181 -255
-300 -118 3
93 136 -88
173 222 17
-164 95 -128
-192 -107 -264
136 -190 -27
-164 -29 -95
-115 -59 -245
-82 -184 136
-228 297 59
-169 -103 -86
-...

output:

0

result:

ok answer is '0'

Test #70:

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

input:

4
1 0 0
2 0 0
2 2 0
2 -1 0
1 2
2 3
2 4
0 1 1
0 0 0
0 2 0
0 0 2
5 6
5 7
5 8

output:

0

result:

ok answer is '0'

Test #71:

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

input:

7
0 0 0
0 3 0
-3 3 0
0 6 0
0 9 0
0 9 3
0 9 -3
1 2
2 3
2 5
3 4
3 6
4 7
0 0 0
2 0 0
2 2 0
4 0 0
6 0 0
6 0 2
6 0 -2
8 9
9 10
9 12
10 11
10 13
11 14

output:

1

result:

ok answer is '1'

Test #72:

score: 0
Accepted
time: 1ms
memory: 4228kb

input:

7
0 0 0
0 3 0
-3 3 0
0 6 0
0 9 0
0 9 3
0 9 -3
1 2
2 3
2 5
3 4
3 6
4 7
0 0 0
2 0 0
2 2 0
4 0 0
6 0 0
6 0 2
6 0 -2
8 9
9 10
9 12
10 11
10 14
11 13

output:

0

result:

ok answer is '0'

Test #73:

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

input:

7
0 0 0
0 3 0
-3 3 0
0 6 0
0 9 0
0 9 3
0 9 -3
1 2
2 3
2 5
3 4
3 6
4 7
0 0 0
2 0 0
2 2 0
4 0 0
6 -4 0
6 0 2
6 0 -2
8 9
9 10
9 12
10 11
10 13
11 14

output:

0

result:

ok answer is '0'

Test #74:

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

input:

4
0 0 0
1 3 0
5 4 0
3 5 3
1 2
1 3
1 4
0 0 0
-1 3 0
-5 4 0
-3 5 3
5 6
5 7
5 8

output:

0

result:

ok answer is '0'

Test #75:

score: 0
Accepted
time: 1ms
memory: 4240kb

input:

3
0 0 0
0 0 1
0 0 2
1 2
1 3
10 4 6
0 0 0
5 2 3
4 5
5 6

output:

1

result:

ok answer is '1'

Test #76:

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

input:

4
0 0 0
1 3 3
-1 5 5
-10 2 2
1 2
1 3
1 4
1 1 6
0 0 0
-1 -1 10
-10 -10 4
5 6
6 7
6 8

output:

1

result:

ok answer is '1'

Test #77:

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

input:

7
0 0 0
1 0 0
-1 0 0
0 1 0
0 -1 0
0 0 1
0 0 -1
1 2
1 3
1 4
1 5
1 6
1 7
0 0 0
2 0 0
-2 0 0
0 2 0
0 -2 0
0 0 2
0 0 -2
8 9
8 10
8 11
8 12
8 13
8 14

output:

24

result:

ok answer is '24'

Test #78:

score: 0
Accepted
time: 1ms
memory: 4104kb

input:

4
0 0 0
89 89 0
-45 -44 109
-44 -45 -109
1 2
1 3
1 4
0 0 0
4 5 11
-9 -9 0
5 4 -11
5 6
5 7
5 8

output:

6

result:

ok answer is '6'

Test #79:

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

input:

5
0 0 0
9 9 0
-5 -4 11
-4 -5 -11
11 -11 1
1 2
1 3
1 4
1 5
0 0 0
4 5 11
-9 -9 0
5 4 -11
11 -11 1
6 7
6 8
6 9
6 10

output:

3

result:

ok answer is '3'

Test #80:

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

input:

4
0 0 0
9 9 0
-5 -4 11
-4 -5 -11
1 2
1 3
1 4
0 0 0
4 5 11
-9 -9 0
5 4 -11
5 6
5 7
5 8

output:

6

result:

ok answer is '6'

Test #81:

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

input:

7
0 0 0
9 9 0
4 5 11
-5 -4 11
-9 -9 0
-4 -5 -11
5 4 -11
1 2
1 3
1 4
1 5
1 6
1 7
0 0 0
89 89 0
44 45 109
-45 -44 109
-89 -89 0
-44 -45 -109
45 44 -109
8 9
8 10
8 11
8 12
8 13
8 14

output:

12

result:

ok answer is '12'

Test #82:

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

input:

7
0 0 0
9 9 0
4 5 11
-5 -4 11
-9 -9 0
-4 -5 -11
5 4 -11
1 2
1 3
1 4
1 5
1 6
1 7
0 0 0
9 9 0
4 5 11
-5 -4 11
-9 -9 0
-4 -5 -11
5 4 -11
8 9
8 10
8 11
8 12
8 13
8 14

output:

12

result:

ok answer is '12'

Test #83:

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

input:

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

output:

3

result:

ok answer is '3'