「各色で塗られたボールはちょうど \(2\) つずつ存在する」という制約より、以下の事柄が成立します。

• 一番上に置かれているボールの色が同じであるような筒の組が複数存在する場合、それらに対してどのような順番で問題文中の操作を行っても答え、すなわち「\(M\) 本の筒全てを空にすることは可能か」という問題に対する判定結果は変わらない。

よって、この問題を解く上では以下のようなシミュレーションが有効です。

以下の操作を \(N\) 回繰り返す。

• 一番上に置かれているボールの色が同じであるような筒の組が存在しないなら、No を出力してプログラムを終了する。
• そうでなく、一番上に置かれているボールの色が同じであるような筒の組が存在するなら、そのうちの一組を適当に選び、問題文中の操作を行う。

\(N\) 回の操作が終わった時点でプログラムが終了していなければ、Yes を出力する。

上記のシミュレーションの計算量は、愚直に行うと \(O(NM^2)\) ないし \(O(NM)\) となります。しかし、\(\text{cnt}[i]:=(\)ある筒の一番上に置かれているようなボールのうち、色が \(i\) であるものの個数\()\) とした配列 \(\text{cnt}\) を用意した上で、それを更新しつつ \(\text{cnt}[i]=2\) となるような整数 \(i\) の集合を queue などを用いて管理することで計算量を \(O(N+M)\) まで改善することが可能です。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
	int N,M; cin >> N >> M;
	queue<int> que;
	vector<queue<int>> A(M);
	vector<vector<int>> mem(N);
	for(int i=0; i<M; i++){
		int k; cin >> k;
		for(int j=0; j<k; j++){
			int a; cin >> a;
			A[i].push(a-1);
		}
		mem[A[i].front()].push_back(i);
	}
	for(int i=0; i<N; i++){
		if(mem[i].size() == 2){
			que.push(i);
		}
	}
	while(!que.empty()){
		int now = que.front(); que.pop();
		for(auto p: mem[now]){
			A[p].pop();
			if(!A[p].empty()){
				mem[A[p].front()].push_back(p);
				if(mem[A[p].front()].size() == 2){
					que.push(A[p].front());
				}
			}
		}
	}
	for(auto p: A){
		if(!p.empty()){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
}