408498: GYM103158 C Topology vs Geometry

Many contestants fear geometry problems for reasons such as precision errors, lack of math background, or unfamiliarity with the problems. Mohammad Yasser recently learned the difference between geometry and topology and found that topology problems are more familiar to competitive programming contestants.

Geometry asks about length, area, volume, angles, and other rigid properties of the shapes. Topology asks about connections and morphology, and other properties that don't change with different transformations like bending or rotation. Mohammad Yasser created an example:

Given an array of 3D triangles, find if the triangles form a triangle mesh. A triangle mesh is a set of connected triangles. Two triangles are directly connected if they both share a side, not just a vertex.

The first line of the input contains one integer T (1 ≤ T ≤ 4) the number of test cases.

The first line of each test case contains a number n (1 ≤ N ≤ 10⁵)  -  the number of the triangles.

N lines follow, each containing 9 integers T_i (0 ≤ T_i ≤ 10⁴) each three consecutive integers represent a vertex of the triangle.

For each test case, output "Yes" if the set of triangles are connected or "No" if they aren't. The checker is case-insensitive so you can output "yEs", "nO", "yes", "NO", etc.

2
3
1000 0 0 0 1000 0 0 999 52
1000 0 0 0 999 52 0 995 105
1000 0 0 0 995 105 0 988 156
3
1000 0 0 0 1000 0 0 999 52
1000 0 0 0 999 52 0 995 105
1000 0 0 0 990 105 0 988 156

Yes
No

2
1
723 266 256 672 193 288 983 379 275
3
806 979 348 759 807 570 341 653 449
723 266 256 983 379 275 167 354 850
678 629 730 806 979 348 768 587 581

Yes
No