10447번 - Deduction 다국어채점 준비 중

Mr. Hong, a private detective, has been summarizing information about the murder cases that he is currently responsible for. Collecting the conduct information of the persons associated with the incident, he was able to construct n statements S₁, S₂, … , S_n. Mr. Hong does not know whether or not each statement is true. Therefore, he called each statement an incident variable. The following six statements show an example of incident variables.

1. S₁ : Cheolsu Kim has a dog.
2. S₂ : Sucheol Park likes cats.
3. S₃ : Heeyoung Ahn likes Sucheol Park.
4. S₄ : (omitted)
5. S₅ : (omitted)
6. S₆ : (omitted)

Investigating the truth of each incident variable and the relationship between variables, he has constructed his deduction based on the result. His deduction consists of one or more assertions which belong to one of the following three types. The first type is that an incident variable S_i is true, the second type is that a set with one or more incident variables has at least one which is false. The last type is that an incident variable S_i proves to be true if one or more variables associated with S_i are all true. These types are represented as follows.

1. Type 1: S_i (S_i is true.)
2. Type 2: S_i1, S_i2, ⋯ , S_ik → ∅ (At least one among S_i1, S_i2, ⋯ , and S_ik is false.)
3. Type 3: S_j1, S_j2, ⋯ , S_jk → S_i (If S_j1, S_j2, ⋯ , and S_jk are all true, then S_i is also true.).

For example, let’s assume that Mr.Hong’s deduction consists of the following eight assertions:

1. ① S₁
2. ② S₂
3. ③ S₁, S₂, S₆ → ∅
4. ④ S₁ → S₆
5. ⑤ S₂ → S₆
6. ⑥ S₁, S₆ → S₃
7. ⑦ S₂, S₄ → S₁
8. ⑧ S₅, S₆ → S₂

The assertions ① and ② belong to Type 1, the assertion ③ belongs to Type 2, and the assertions ④ , ⑤ , ⑥ , ⑦ , ⑧ belong to Type 3. In order to prove that his deduction is valid, he should show that there aren’t any contradictions between the assertions of the deduction and that there are no assertions that belong to Type 3 such that the variable on the right side of ‘→’ must be false even though all variables on the left side are all  true. (Notice that if there exists a variable on the left side of ‘→’ which is false, the truth of the variable on the right side does not infringe the validity of the deduction.)

A valid assignment means a truth assignment to the incident variables that makes a deduction valid. Mr. Hong wants to know if there is a valid assignment that makes his deduction valid.

In the above example, since both of S₁ and S₂ are true by assertions ① and ② , S₆ must be false by Hong’s deduction is not valid. If the assertion ③ is excluded from his deduction, there exists a valid assignment, which is that all variables are assigned as true or that only S₄ is assigned as false.

Given Mr. Hong’s deduction with n incident variables, write a program that determines whether or not there is a valid assignment.

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing four integers n, m₁, m₂, m₃ (1 ≤ n ≤ 1,500, 1 ≤ m₁ < n, 0 ≤ m₂, m3 ≤ 1,500), where n is the number of incident variables and m₁, m₂, m₃ are the numbers of Type 1, Type 2, and Type 3 assertions of Mr. Hong’s deduction, respectively. Each of the following m₁ lines contains an integer i (1 ≤ i ≤ n) representing a Type 1 assertion, i.e., an incident variable S_i . Each of the following m₂ lines contains k + 1 integers k, i₁,i₂, … , and i_k (1 ≤ k, i₁, i₂, … , i_k ≤ n, i_r ≠ i_s for r ≠ s) representing a Type 2 assertion “S_i1, S_i2, ⋯ , S_ik → ∅”. Each of the following m₃ lines contains k + 2 integers k,j₁,j₂, … ,j_k, and i (1 ≤ k ≤ n − 1 , 1 ≤ j₁,j₂, … ,j_k,i ≤ n , j_r ≠ j_s for r ≠ s, i ≠ j_r for 1 ≤ r ≤ k) representing a Type 3 assertion “S_j1, S_j2, ⋯, S_jk → S_i”.

Your program is to write to standard output. Print exactly one line for each test case. The line should contain “YES” if the deduction is valid, otherwise, “NO”.