Consider the decision problem 1-intersect. Given subsets S₁, ..., S_m of [n], return yes if there is a subset A [n] such that for all j [m], we have |S_j A| = 1. Otherwise, return no. As an example, let n = 6 and consider the instance consisting of the following subsets.

S1 = {1, 2}, S2 = {1, 5, 6}, S3 = {3, 4, 5, 6}, S4 = {2, 3, 6}, S5 = {2, 4, 6}

The correct output for this instance is yes since choosing A = {2, 5} will intersect each S_j once. Prove that 1-intersect is NP-complete. Hint: Recall the 3-coloring problem.