Explanation

If we only have two players $x$ and $y$, then we have 4 cases.

• If $x$ vouches for $y$ and $x$ is an imposter, then $y$ must also be an imposter.

• If $x$ vouches for $y$ and $x$ is a crewmate, then $y$ must also be a crewmate.

• If $x$ accuses $y$ of being an imposter and $x$ is an imposter, then $y$ must be a crewmate.

• If $x$ accuses $y$ of being an imposter and $x$ is a crewmate, then $y$ must be an imposter.

You'll notice that whenever $x$ accuses $y$, they'll always be of a different type, and when $x$ vouches for $y$, they'll always be of the same type.

With this information, we can build a bipartite graph and color nodes with the same color if they vouch for each other, or different colors if one of them accuses the other. If we can't build this graph, then no valid arrangement can exist.

Otherwise, we'll consider each connected component independently and keep track of the number of crewmates and imposters. At the end, we'll return the sum of the maximum of these two values for all connected components. We don't care about the roles of each node because we can switch all of them to get another valid solution.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main() {
	int t;
	cin >> t;
	for (int tc = 0; tc < t; tc++) {

Copy
import java.io.*;
import java.util.*;

public class AmongUs {
	private static class Edge {
		public int first;
		public boolean second;

		public Edge(int first, boolean second) {
			this.first = first;

Copy
for _ in range(int(input())):
	n, q = map(int, input().split())

	"""
	adj[i][j] = {the jth adjacent node from i,
	their statement (0 = imposter, 1 = crewmate)}
	"""
	adj = [[] for _ in range(n)]

	for _ in range(q):