Problem Description

In the country of JOI, there are $ N $ councilors numbered from $ 1 $ to $ N $. As the minister of JOI, you are trying to identify the spies among the councilors. You have obtained the following information for each councilor $ i $ ($1 \leq i \leq N$):

• If $ T_i = 1 $, councilor $ i $ is a spy.
• If $ T_i = 2 $, councilor $ i $ is not a spy.
• If $ T_i = 3 $, it is unknown whether councilor $ i $ is a spy or not.

Additionally, through interrogation, you have obtained $ M $ new pieces of information. The $ j $-th piece of information ($1 \leq j \leq M$) is that councilor $ A_j $ ($1 \leq A_j \leq N$) testified that councilor $ B_j $ ($1 \leq B_j \leq N$) is a spy and councilor $ C_j $ ($1 \leq C_j \leq N$) is not a spy.

However, if councilor $ A_j $ is a spy, the testimony in the $ j $-th piece of information is false. That is, if councilor $ A_j $ is a spy, at least one of the statements "councilor $ B_j $ is a spy" or "councilor $ C_j $ is not a spy" is not true. On the other hand, if councilor $ A_j $ is not a spy, the testimony in the $ j $-th piece of information may or may not be true.

Given the information about each councilor and the results of the interrogation, write a program to determine if the $ N + M $ pieces of information are contradictory. If they are not contradictory, determine whether each councilor is a spy or not. If there are multiple solutions that match the $ N + M $ pieces of information, you may output any one of them.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ T_1 $ $ T_2 $ $\cdots$ $ T_N $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $\vdots$ $ A_M $ $ B_M $ $ C_M $

Output Format

Output to the standard output.

If the given information is contradictory, output -1 in one line.

Otherwise, the output consists of $ N $ lines. The $ i $-th line ($1 \leq i \leq N$) should contain $ 1 $ if councilor $ i $ is a spy, and $ 2 $ if councilor $ i $ is not a spy. If there are multiple solutions that match the $ N + M $ pieces of information, you may output any one of them.

Sample Input and Output

Sample Input #1

4 1
1 3 2 3
1 2 3

Sample Output #1

1
2
2
1

Sample Input #2

4 2
2 1 3 1
4 3 1
2 4 3

Sample Output #2

-1

Sample Input #3

3 2
1 2 2
2 1 3
2 3 1

Sample Output #3

1
2
2

Notes/Hints

Constraints

• $1 \leq N \leq 300,000$.
• $1 \leq M \leq 300,000$.
• $1 \leq T_i \leq 3$ ($1 \leq i \leq N$).
• $1 \leq A_j \leq N$ ($1 \leq j \leq M$).
• $1 \leq B_j \leq N$ ($1 \leq j \leq M$).
• $1 \leq C_j \leq N$ ($1 \leq j \leq M$).
• $A_j \neq B_j$ ($1 \leq j \leq M$).
• $A_j \neq C_j$ ($1 \leq j \leq M$).
• $B_j \neq C_j$ ($1 \leq j \leq M$).

Subtasks

1. ($ 7 $ points) $N \leq 16$, $M \leq 100$.
2. ($ 38 $ points) $N \leq 3,000$, $M \leq 3,000$.
3. ($ 55 $ points) No additional constraints.

Sample Explanation 1

In the sample output #1, councilor $ 1 $ is a spy, and the testimony "councilor $ 2 $ is a spy and councilor $ 3 $ is not a spy" is false because councilor $ 2 $ is not a spy. Therefore, the sample output #1 matches the given information and is a correct answer. Another correct answer is that only councilor $ 1 $ is a spy and the others are not.

Sample Explanation 2

If councilor $ 3 $ is a spy, it does not match the first piece of information from the interrogation. If councilor $ 3 $ is not a spy, it does not match the second piece of information from the interrogation. The information is contradictory, so -1 should be output.

Sample Explanation 3

In sample input #3, all councilors have information about whether they are spies or not, and this matches the information from the interrogation. Therefore, the sample output #3 is the only correct answer. Note that the testimony of a councilor who is not a spy may or may not be true.

见题面 Input 部分

见题面 Output 部分