4. Delíme sa s jedlom

Vedúci KSP sa stretli na chate. Ako tomu už ale býva, každý sa spolieha na to, že ostatní donesú na chatu dostatok jedla, aby sa niečo ušlo aj jemu. Vedúci, ktorý si doniesol jedlo, ho má dosť pre každého na chate, no nie je vždy ochotný podeliť sa s ostatnými. Vyšlo to nakoniec ale tak, že v každej dvojici vedúcich je práve jeden z nich ochotný podeliť sa o svoje jedlo s tým druhým vedúcim z tejto dvojice.

Paulínku zaujímalo, koľko najmenej vedúcich muselo doniesť jedlo a ktorí konkrétni vedúci ho museli doniesť na to, aby nikto na chate netrpel hladom. Pomôžete jej zodpovedať túto otázku?

Úloha

Máme \(n\) vedúcich, pričom pre každú dvojicu vedúcich \(i, j\) je vždy práve jeden z nich ochotný podeliť sa s tým druhým o jedlo (ak nejaké doniesol). Každý vedúci, ktorý doniesol jedlo, ho doniesol dostatočne veľa na to, aby sa s ním vedel podeliť s kýmkoľvek, komu je ochotný toto jedlo dať, a aby niečo ostalo aj pre neho samotného. Ak však niekto dostane jedlo od niekoho iného, toto jedlo si ponechá a nedá ho už nikomu ďalšiemu, keďže to nie je jeho vlastné jedlo.

Nájdite čo najmenšiu podmnožinu vedúcich takú, že keď všetci vedúci z tejto podmnožiny donesú jedlo, tak pre každého vedúceho platí, že doniesol jedlo alebo že existuje vedúci, ktorý doniesol jedlo a je ochotný podeliť sa s ním (ide o logické alebo, teda môžu nastať aj oba prípady naraz).

Formát vstupu

V prvom riadku vstupu sú dve medzerou oddelené čísla - číslo \(n\) (\(1 \leq n \leq 1000\)) udávajúce počet vedúcich, ktorí prišli na chatu, a číslo \(s\) označujúce číslo aktuálnej sady vstupov (\(s = 0\) v prípade, že sa jedná o sample, inak \(s \in {1, 2, 3, 4}\) podľa čísla aktuálnej sady).

V každom z nasledujúcich \(n\) riadkov je \(n\) čísel, z ktorých každé je buď 0, alebo 1. Označme \(j\)-te číslo v \(i\)-tom z týchto riadkov ako \(A_{ij}\). Ak \(A_{ij} = 1\), znamená to, že vedúci \(i\) je ochotný podeliť sa s vedúcim \(j\) o svoje jedlo, inak vedúci \(i\) nie je ochotný podeliť sa s vedúcim \(j\) o svoje jedlo. Špeciálne pre každé \(i\) je \(A_{ii}\) tiež rovné nule, keďže nedáva zmysel, aby sa vedúci sám so sebou delil o jedlo.

Zároveň pre každú dvojicu rôznych vedúcich \(i, j\) platí, že buď vedúci \(i\) je ochotný podeliť sa s vedúcim \(j\) o svoje jedlo, alebo vedúci \(j\) je ochotný podeliť sa s vedúcim \(i\) o svoje jedlo (teda nastáva práve jeden z týchto prípadov).

Formát výstupu

Vypíš dva riadky. V prvom z nich vypíš jedno celé číslo \(k\), a to čo najmenší počet vedúcich, ktorí museli na chatu doniesť jedlo, aby sa každý vedúci mohol najesť. Tento počet nemusí byť nutne najnižší možný, ale stačí, že nebude vyšší než nejaký limit \(k_{\max}\), ktorý je pre každú sadu rozdielny a v každej ďalšej sade sa postupne znižuje, viď. časť Hodnotenie. V druhom riadku následne v ľubovoľnom poradí vypíš čísla \(k\) vedúcich, ktorí museli doniesť na chatu jedlo. Vedúcich číslujeme od \(1\) do \(n\).

Hodnotenie

Sú 4 sady vstupov, v každej platí \(1 \leq n \leq 1000\). Body za jednotlivé sady sú následne udeľované podľa maximálnej hodnoty \(k\), ktorú Tvoj program bude potrebovať spomedzi vstupov pre danú sadu. V jednotlivých sadách tak pre získanie bodov za danú sadu platia nasledujúce obmedzenia:

Ak Tvoj program prekročí časový limit v ľubovoľnom vstupe alebo vypíše skupinu vedúcich, ktorá nezaručí to, že každý vedúci bude mať prístup k jedlu, tak Tvoj program skončí chybovou hláškou (TLE v prvom prípade a WA v druhom prípade) a nedostaneš žiadne body za danú sadu. Podobne ak v nejakom vstupe prekročíš hodnotu \(k_{\max}\) danej sady, Tvoj program skončí chybou WA a nedostaneš za danú sadu žiadne body.

V popise k tejto úlohe okrem popísania postupu, ktorým Tvoj program vyberá vhodné podmnožiny vedúcich, nezabudni tiež napísať hodnotu \(k\), ktorú tento postup v najhoršom prípade dosahuje, spolu s dôkazom tejto hornej hranice veľkosti vybratej podmnožiny. Okrem toho tiež popíš a zdôvodni časovú a pamäťovú zložitosť svojho algoritmu, hoci sa pri hodnotení na ne nebude klásť až taká váha, ako na veľkosť horného odhadu hodnoty \(k\) a na dôkaz toho, že ju popísaný postup nikdy neprekročí.

Príklady

Input:

3 0
0 1 1
0 0 0
0 1 0

Output:

1
1

Vedúci \(1\) je ochotný podeliť sa o jedlo s obomi zvyšnými vedúcimi, preto stačí, aby doniesol jedlo iba on.

Input:

4 0
0 1 0 0
0 0 1 0
1 0 0 1
1 1 0 0

Output:

2
2 4

Vedúci \(1, 2, 3, 4, 1\) v tomto poradí tvoria cyklus toho, kto je komu ochotný dať jedlo, preto stačí vybrať napríklad každého druhého vedúceho v tomto cykle. Ak by doniesol len jeden vedúci jedlo, nestačilo by to na nasýtenie každého.