If there are no confused villagers, when villager \(i\) testifies that villager \(j\) is honest, it means that villagers \(i\) and \(j\) have the same attribute (honest or liar). If they testify that someone is a liar, it means the opposite. Therefore, the condition that there are no contradictions in the testimonies is equivalent to the graph where edges representing testimonies of “honest” have weight \(0\) and those of “liar” have weight \(1\) being a bipartite graph (with weights).

If villager \(i\) is confused, the weights of the edges corresponding to villager \(i\)’s testimonies are reversed. Now, consider the following graph:

• It has a total of \(2N\) vertices, vertices \(U_i\) representing the villagers themselves and vertices \(V_i\) representing the villagers’ testimonies.
• For each testimony, add an edge of weight \(C_i\) between \(V_{A_i}\) and \(U_{B_i}\).
• Add an edge between \(U_i\) and \(V_i\) of weight \(0\) if villager \(i\) is not confused, and weight \(1\) if they are confused.

Here, we need to span the edges of the second type so that the graph is bipartite. Therefore, using a Union-Find data structure with potentials, we can:

• First, add the edges of the first type. If the graph is not bipartite at this point, there is no assignment that satisfies the conditions.
• Next, in any order, add the edges of the second type, assigning weights that do not conflict with the potential differences (if they are not yet connected, assign any weight).

By doing this, we can construct an assignment that satisfies the conditions, or detect that it is impossible.

Sample implementation: https://atcoder.jp/contests/arc188/submissions/60033237