Sharing Pepero 2

Subtask 1 For $K$ empty cells, enumerate all $2^K$ assignments and check that every student receives both flavors. This takes $O(2^K NM)$ time.

Full solution Create one vertex for each row and column, and an edge between row $i$ and column $j$ for every empty cell $(i,j)$. A horizontal box directs its edge toward the row; a vertical box directs it toward the column. Call a vertex required if its row or column contains a student. The goal is exactly to give every required vertex positive indegree.

In a tree component there is one fewer edge than vertices. If all vertices are required, the goal is impossible. Otherwise root the tree at a nonrequired vertex and direct every tree edge toward its child. Every other vertex receives an incoming edge.

For a component containing a cycle, choose a spanning tree and a nontree edge $(r,c)$. Root the tree at $r$, direct tree edges toward children, and direct the chosen extra edge toward $r$. Every vertex now has an incoming edge. All other edges may be directed arbitrarily. An isolated vertex is covered by the same tree rule.

Therefore, impossibility occurs exactly when a tree component has only required vertices. Use DSU to build a spanning forest and collect extra edges, choose roots, and traverse iteratively to construct the assignment. Time complexity is $O(NM\alpha(N+M))$ and space complexity is $O(NM+N+M)$.

Solution written by GPT6.1