Norela
Time limit1sMemory limit512 MB
Given up to 24 spells, each flipping a specified set of cards, choose the fewest spells (smallest lexicographic index list) so every card ends face up.
- Level
Medium7 of 10
- Topics
- Bit manipulation, Greedy, Math, Brute force
- Solved
- No attempts yet
Problem
Adrian the 3rd is a wizard prince. On International Wizard's Day (the 4th of November) he wanted to impress Norela, his dream girl. He has n playing cards, which are initially put with the face down on a table. Adrian can use m spells, a spell has the format: q a1 a2 … aq. If Adrian uses a spell, the playing cards with the indices a1 a2 … aq will be turned in order. (Integers a1 a2 … aq are all different). The card will be turn face up if it is face down and will be turned face down if it is face up and all spells can be used no more than one time. Help Adrian impress Norela before his nemesis Manea Long Eyebrow does it!
Find the minimum number of spells that have to be used to turn all n cards face up, also determinate the indices of the used spells. If there are more solutions, print the minimum lexicographical answer.
Input
The first line contains two integers n and m.
The next m lines contain the description of every spell q a1 a2 … aq, where q is the number of cards that will be turned by that spell and a1 a2 … aq are the indices of those cards.
Output
The first line will contain only one integer representing the minimum number of used spells and the second line will contain the indices of those spells. If there are more solutions with minimum number of used spells, there will be printed the minimum lexicographical answer.
Constraints
- n ≤ 60
- m ≤ 24
Hint
A set of integers a1 a2 … an is lexicographically smaller than other set b1 b2 … bn if there is a k between 1 and n so that a1=b1, a2=b2, ..., ak-1 = bk-1 and ak < bk.