Ема е голем фан на криптовалутите (особено на биткоин), и таа користи разни уреди за “копање” на биткоини. Со растот на оваа валута, таа сега сака да вложи дополнителни средства и да купи нови уреди од најблиската специјализирана продавница.

Во продавницата се продаваат поголем број на уреди, и некои од нив може да се директно зависни од други за да функционираат правилно. Значи, ако уредот X зависи од уредот Y тогаш, ако е купен уредот Х мора да е купен и Y бидејќи Х не може да функционира без Y. Ако не е купен Y, излегува дека Х е купен за џабе.

Од горното јасно е дека и доколку некој уред X зависи од уред Y, и уред Y зависи од уред Z, тогаш не можеме да го земеме X без да го земеме Z. Велиме дека Х е индиректно зависен од Z.

Продавницата каде што отишла Ема има уреди само од најновата CRYPTO генерација, за која што важи уште едно интересно правило: имено, ако уред X зависи од некои уреди Y и Z, тогаш за Y и Z знаеме дека:

   - Y зависи од Z, или
   - Z зависи од Y, или
   - и двете се зависни едно од друго (Y од Z и Z од Y).

Ова важи како за директни зависности, така и за индиректни зависности.

Доколку го знаете бројот N на уреди во продавницата, и ви се познати сите директни зависности меѓу уредите, утврдете колку различни вредности постојат за бројот на уреди кои Ема може да ги купи. Со други зборови, утврдете за кои од вредностите 1, 2, 3... N постои подмножество уреди со толку елементи кои купени заедно ќе функционираат правилно.

Влез

Во првиот ред е запишан еден цел број N (1 <= N <= 50), бројот на уреди во продавницата.

Во секој од следните N редови се запишани по N цели броеви Dij (0 <= Dij <= 1), кои означуваат дали i-тиот уред е директно зависен од j-тиот уред (Dij=1 ако постои таква зависност). Во првиот од овие N редови се дадени зависностите на првиот уред, итн.

Во влезот, секогаш ќе важи Dii=0 (нема да е означено дека уред зависи сам од себе). Дополнително, секогаш ќе важи и правилото за зависност од текстот на задачата (ако уред X зависи од некои уреди Y и Z, тогаш Y зависи од Z, или Z зависи од Y, или и двете се зависни еден од друг).

Забелешка: Во тест случаи кои носат најмалку 6% од поените, нема да постојат зависности (Dij = 0)
Во други тест случаи кои носат најмалку 9% од поените, ќе важи N <= 5.
За дополнителни 15% од поените, ќе важи N <= 20.

Излез

Во еден ред, во растечки редослед, отпечатете ги сите можни вредности за бројот на уреди кои може да ги купи Ема. На пример, доколку постои едно или повеќе валидни подмножества од 3 уреди кои може да ги купи Ема, понатаму слично од 5 уреди и од 7 уреди, треба да ги отпечатете вредностите 3, 5 и 7, по редослед, во еден ред.

Ограничувања

Временско ограничување: 500 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
4
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0

излез
4

влез
5
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 1 0 1
1 0 0 0 0

излез
1 2 3 4 5

Објаснување за првиот пример: Мора да се земат сите 4 уреди, бидејќи првиот зависи од вториот, вториот од третиот, третиот од четвртиот, а четвртиот од првиот. Значи, не постои подмножество со еден уред, подмножество со 2 уреда и подмножество со 3 уреда кои ги исполнуваат условите. Затоа излезот е само 4.

Објаснување за вториот пример: Може да се земе само еден уред (на пример, првиот), два уреди (на пример, првите два, бидејќи не зависат од никого), три уреди (на пример, првиот, вториот и петтиот), четири уреди (на пример, првиот, третиот, четвртиот и петтиот) или (сите) пет уреди.