Hall 定理：
对于二分图 \(G = (X, Y, E)\)，\(|X| \le |Y|\)，若是 \(X\)-完美匹配存在（即所有 \(X\) 中的点都有匹配点），则充要条件是 \(\forall W \subseteq X, |W| \le |N_G(W)|\)，其中 \(N_G(W)\) 为与 \(W\) 中点相邻的点集。
说人话就是对于 \(X\) 的所有子集，\(Y\) 中都有足够的点与之匹配。证明参见 OIWiki。
这个定理有啥用呢，看 这题，其实就是要把人看成左部点，特产看成右部点，然后其实就是在求一个最大的 \(k\)，使得每个左部点恰好唯一匹配 \(k\) 个右部点，且每个右部点不被重复匹配。
怎么去想呢，有一个叫 k-star matching 的结论说的就是上面这个条件相当于把每个左部点拆成 \(k\) 个右部点，然后就等价于存在 \(X\)-完美匹配了。于是根据 Hall 定理，\(\forall S, |N_G(S)| - k|S| \ge 0\)，化简得 \(k \le \dfrac{|N_G{S}|}{|S|}\)，于是可以使用 bitset 直接暴力枚举做到 \(\large{\mathcal{O}(\dfrac {m(n + qc \log n + q2^c)}{\omega})}\)