Problem E: United Word Volunteering
United Word Volunteering (UWV) is a non-profit organization focusing in educational and medical volunteering programs in developing countries around the world.
At the end of each trimester UWV distributes the volunteers registered to
one of their chosen programs. This assignment cannot be random, since each volunteer can select the programs s/he wants to participate based on his/her skills and preferences. Notice that a volunteer may decide not to participate in any program running that trimester. Furthermore, each volunteering program has a maximum number of volunteers that can participate.
UWV wants to verify if it is possible to assign all registered volunteers to
one of their favorite programs. If a volunteer does not select any program, you can consider a successful assignment for that particular volunteer.
You must write a program to determine if all volunteers can participate in one of the programs of their choice.
The first line of the input contains a number T of test cases. For each test case, there is a line with two numbers P and V, separated by a single space. P is the number of volunteering programs and V is the number of registered volunteers. Programs are identified by integers, ranging from 1 to P. Volunteers are identified by integers, ranging from 1 to V.
Each of the following P lines contains an integer M, that states the maximum
number of volunteers that can participate in that program. Each of the following V lines describes the programs selected by each volunteer. It starts with a number N that specifies the number of programs selected by that volunteer, followed by N integers representing the selected programs.
- 1 ≤ T ≤ 10
- 1 ≤ P ≤ 100
- 1 ≤ V ≤ 300
- 1 ≤ M ≤ 10
- 0 ≤ N ≤ 10
For each test case the program has to print a line containing YES if it is possible to assign all volunteers to one of their chosen programs, or NO, otherwise.
2 1 3
2 1 2
2 2 3
2 1 3