P9792 [NERC 2018] Bimatching

Translated from Problem B of [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf).

You are holding a dance party with some friends. At this party, there are $n$ men and $m$ women. Originally, the dance is done in male-female pairs, but because there are not enough men, you cannot give every woman a male partner. So you invent a new dance form: one man pairs with two female partners. Of course, when choosing partners, each woman gives a rating to each man. If the rating is $1$, it means the woman is willing to dance with that man. Only when both women are willing to dance with that man can they form a partner group. As the organizer, you need to find the maximum number of such partner groups that can be formed, with the requirement that **no person can appear in more than one group**.

The first line contains an integer $t (1 \leq t \leq 20)$, the number of test cases. Then follow $t$ test cases. In each test case, the first line contains two integers $n$ and $m$. It is guaranteed that $1 \leq n,m$ and $n + m \leq 150$. Then follows an $n \times m$ matrix, where $a_{i,j}$ indicates whether woman $j$ is willing to dance with man $i$.

For each test case, output one line containing the maximum number of partner groups that can be formed.

The Constraints guarantee $1 \leq t \leq 20$, $1 \leq n, m$, and $n + m \leq 150$. The figures below explain Sample 1 and Sample 2, where the bold parts show one feasible solution. Sample 1:  Sample 2:  Translated by ChatGPT 5