HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Exhaustive search & Backtracking > problem:


50486 - Problems and Programmers

Guest
• Review clarifications (1)

Section problems

• 50714 - The knight
• 50713 - Castle and the girls
• 50710 - Permutations
• 50709 - k-ary Strings
• 50708 - Binary Strings
• 50996 - Checkers - the shortest path
• Check-Mate
• 50479 - Bit Compressor
• 50486 - Problems and Progra...
• 50712 - Moon algebra
• 50717 - Hurdle Jumping
• 50840 - Tanker trucks
• 50490 - Across the River
• 50828 - Arranging Time Table
• 51067 - Jumping frog
• 51142 - Jump Min Value
• 51082 - Sum is equal to K - 1

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Osman Ay.

Problems and Programmers

A group of N teachers are assigned to solve M programming problems in a teacher professional development program. Every teacher chooses the problems he can solve. Since teachers are always busy, they want to make a possible smallest team to solve the given problems. What is the size of the smallest team that can solve all the problems?

Input specification
The first line of the input contains two integers N (1 ≤ N ≤ 20) and M (1 ≤ M ≤100). Each of the following N lines denotes the problems a teacher can solve with a set of K+1 integers. The first integer (K) is the number of the problems and the following K numbers are the problem IDs.

Output specification
The output contains a single integer that is number of the teachers in the smallest team. If it is not possible to solve all the problems, print the word "impossible".

Sample Input I
7 10
3 1 2 7
3 2 7 8
2 10 4
2 3 4
4 2 3 4 5
3 5 6 4
3 7 5 9
Sample Output I
6



Для отправки решений необходимо выполнить вход.

www.contester.ru