Егер \(nm \le 200\), онда \(n \le 20\) немесе \(m \le 10\) бірі дұрыс болады.

Егер \(n \le 20\) болса, динамиканы \(dp[cities]\) есептейміз — қалалар жиынтығы үшін ең аз жауап (оларды \(0 \le cities < 2^n\) сан маскасында сақтаймыз). \(2m\) мүмкін ауысу бар, әрқайсысы \(O(1)\): фактіні және осы фактінің шындылығын қарап шығамыз, осы мәнге сәйкес қалалар маскасын алдын ала есептеп, оны \(cities\) жиынтығымен қиылыстырамыз.

Егер \(m \le 10\) болса, барлық \(3^m\) факт жинақтарын олардың мәндерімен қарап шығамыз, яғни әр факт үшін \(3\) нұсқа бар: шындық, жалған және бұл факт туралы білмейміз. Әр факт таңдауына сәйкес осы жиынтық анықтайтын қалалар жиынтығын есептеп, борда сақтаймыз және сұраныстарға бор бойынша түсумен жауап береміз.

Так как \(nm \le 200\), то одно из \(n \le 20\) и \(m \le 10\) верно.

Если \(n \le 20\) посчитаем динамика \(dp[cities]\) – минимальный ответ для множества городов cities (будем хранить их в маске числа \(0 \le cities < 2^n\)). Есть \(2m\) возможных переходов, каждый за \(O(1)\): перебираем факт и истинность этого факта, вытаскиваем предпосчитанную маску городов соответствующую этому значению факта и берем пересечение с \(cities\).

Если \(m \le 10\), то переберем все \(3^m\) наборы фактов с их значениями, то есть для каждого факта есть \(3\) варианта: правда, ложь и мы не знаем об этом факте. Для каждого выбора фактов вычислим множество городов которое этот набор определяет, сохраним в боре и будем отвечать на запросы за спуск по бору.