ЗДРАВОСЛОВНО ХРАНЕНЕ

Един хубав слънчев ден, Мечо Пух решил да отиде на гости на стария си познайник – Карлсон, който живее на покрива. След като прекарали няколко часа, наблюдавайки небето от покрива на сградата, Пух и Карлсон решили да отидат на гости на Дребосъчето. 

В дома на Дребосъчето, те открили тайните запаси с храна на майката му. Запасите съдържали огромни количества от различни видове кюфтенца, тортички, сладолед, медени изделия и други. Тъй като станало време Мечо Пух да се прибира в Голямата гора, те решили да разпределят запасите в два чувала, като всеки вземе по един. 

Като разбрало какви количества храна се готвят да изядат неговите приятели, Дребосъчето се разтревожило за тяхното здраве. Това, което най-много го притеснило, било вредното въздействие на някой комбинации от храна. Например, според него никак не е полезно да се комбинират кюфтенца с мед или риба с боза и сладолед. Колкото повече съставки съдържа една вредна комбинация, толкова по-опасна е тя.

Помогнете на Дребосъчето да разпредели храната в двата чувала, като напишете програма NUTRITION, която по зададени хранителни продукти и списък с вредни комбинации, намира  разпределение на продуктите в двата чувала, с възможно най-малка обща вреда за здравето(ОВЗ).

Общата вреда за здравето за дадено разпределение се пресмята, като сума от броя на елементите на всички вредни комбинации, всички части на които се намират в един и същ чувал (т.е. ще бъдат изядени от един и същ приятел на Дребосъчето). Всички хранителни продукти трябва да бъдат разпределени в някой от двата чувала (все пак Пух и Карлсон няма да се съгласят да оставят неизядена храна).

Входните данни се четат от файл NUTRITION.IN. На първия ред е записано числото N (N ≤ 1 100), което задава броя на всички хранителни продукти в тайните запаси. За удобство, хранителните продукти са номерирани с числата от 1 до N. На следващия ред е записано числото M (М ≤ 250) – броят на вредните комбинации известни на Дребосъчето. Следващите M реда съдържат информация за една вредна комбинация, като първото число задава броя на хранителните продуктите участващи в нея, а останалите – техните номера. Една комбинация не може да съдържа един и същ хранителен продукт повече от веднъж.

Изходните данни се печатат във файл NUTRITION.OUT. Програмата трябва да отпечата на един ред броя на хранителните продукти, които ще постави в първия чувал и  номерата на тези продукти. Всички числа в изходния файл трябва да бъдат на отделен ред. Всички продукти, които не бъдат поставени в първия чувал, се считат за поставени във втория.

За всеки тест, максимален брой точки ще получи състезателят, чиято програма е намерила разпределение с най-малко ОВЗ. Всички останали решения ще получат точки пропорционално на ОВЗ на разпределението, намерено от тяхната програма. Програмата на участника трябва да завърши един тест за не повече от 5 секунди.

ПРИМЕР:
NUTRITION.IN
5
8
2 1 2
2 1 3
2 1 4
2 2 3
3 1 3 4
1 5
2 3 5
2 4 5	NUTRITION.OUT
3
1
2
4

	

ПОЯСНЕНИЕ: В първия чувал се поставят три хранителни продукта с номера 1, 2 и 4, като във втория остават два хранителни продукта с номера 3 и 5. Продукти 1 и 2 се намират в един и същ чувал, следователно имат ОВЗ равна на 2. Продукти с номера 1 и 4 се намират в един и същ чувал, следователно имат ОВЗ равна на 2. Продукти 3 и 5 имат ОВЗ равна на 2. Продукт 5 сам по себе си носи ОВЗ равна на 1. Няма други комбинации, частите на които се намират в един и същ чувал, следователно общата вреда за здравето в това разпределение е равна на 2 + 2 + 2 + 1 = 7. Съществуват разпределения с ОВЗ равна на 3.