import std.algorithm, std.array, std.conv, std.stdio, std.typecons; class Triangle { uint A, B, C; Triangle nAB, nBC, nAC; // the triangles that share the edges int orientation; this (uint a, uint b, uint c) { A = a, B = b, C = c; assert(A < B && B < C); } // false if already set void set_neighborhood(Triangle n, uint P, uint Q) { if (tuple(P, Q) == tuple(A, B)) { nAB = n; } else if (tuple(P, Q) == tuple(B, C)) { nBC = n; } else if (tuple(P, Q) == tuple(A, C)) { nAC = n; } else assert(0); } // X is A, B or C // 1: A->B->C, -1: A->C->B uint perm(uint X, int o = 0) { if (o == 0) o = this.orientation; if (o == 1) { if (X == A) return B; else if (X == B) return C; else if (X == C) return A; else assert(0); } else if (o == -1) { if (X == B) return A; else if (X == C) return B; else if (X == A) return C; else assert(0); } else assert(0); } } class Triangulation { Triangle[] triangles; bool unorientable = false; this(uint[][] tri_array) { // remove multiple appearance bool[Tuple!(uint, uint, uint)] triangle_set; foreach (tri3; tri_array) { triangle_set[tuple(tri3[0], tri3[1], tri3[2])] = true; } this.triangles = triangle_set.keys.map!(t => new Triangle(t[0], t[1], t[2])).array; // set neighborhoods Triangle[Tuple!(uint, uint)] edges; uint[Tuple!(uint, uint)] edge_appear_times; foreach (triangle; triangles) { foreach (edge; [tuple(triangle.A, triangle.B), tuple(triangle.B, triangle.C), tuple(triangle.A, triangle.C)]) { if (auto neiborhood = edge in edges) { // shared by three triangles if (edge_appear_times[edge] >= 2) { unorientable = true; return; } // set neighborhoods edge_appear_times[edge]++; triangle.set_neighborhood(*neiborhood, edge[0], edge[1]); neiborhood.set_neighborhood(triangle, edge[0], edge[1]); } else { // set neighborhoods edges[edge] = triangle; edge_appear_times[edge] = 1; } } } } // DFS void give_orientation(Triangle triangle, uint P, uint Q) { // already set if (!triangle || triangle.orientation != 0) return; triangle.orientation = triangle.perm(P, 1) == Q ? 1 : -1; // recursively if (triangle.perm(triangle.A) == triangle.B) give_orientation(triangle.nAB, triangle.B, triangle.A); else give_orientation(triangle.nAB, triangle.A, triangle.B); if (triangle.perm(triangle.B) == triangle.C) give_orientation(triangle.nBC, triangle.C, triangle.B); else give_orientation(triangle.nBC, triangle.B, triangle.C); if (triangle.perm(triangle.A) == triangle.C) give_orientation(triangle.nAC, triangle.C, triangle.A); else give_orientation(triangle.nAC, triangle.A, triangle.C); } bool is_orientable() { if (unorientable) return false; foreach (triangle; triangles) { give_orientation(triangle, triangle.A, triangle.B); } // check foreach (triangle; triangles) { with (triangle) // A -> B -> C -> A if (orientation == 1) { if ((nAB && nAB.perm(B) != A) || (nBC && nBC.perm(C) != B) || (nAC && nAC.perm(A) != C)) return false; } // A -> C -> B -> A else if (orientation == -1) { if ((nAB && nAB.perm(A) != B) || (nBC && nBC.perm(B) != C) || (nAC && nAC.perm(C) != A)) return false; } else assert (0); } return true; } } void main() { auto M = readln[0 .. $-1].to!uint; uint[][] tris; foreach (m; 0 .. M) tris ~= readln.split.to!(uint[]); auto trig = new Triangulation(tris); writeln(trig.is_orientable ? "YES" : "NO"); }