Majoritatea copiilor sunt sociabili și relaționează ușor cu cei de vârsta lor dar sunt și copii mai timizi sau mai puțin atrași de activitățile de grup. În urma studierii comportamentului unui eșantion de n copii, s-a stabilit, pentru fiecare doi copii dacă relaționează sau nu. Pentru serbarea de sfârșit de an, s-a propus realizarea unei scenete și este necesară selectarea unei grupe cât mai numeroase de micuți dar fără a depăși k, numărul maxim de personaje. Rolurile presupun interacțiunea fiecărui copil selectat cu toți ceilalți mici actori care joacă în scenetă.

Cerința

Cunoscând n – dimensiunea eșantionului studiat, capacitatea fiecărui copil de a relaționa cu ceilalți și k – numărul maxim de personaje din scenetă, să se determine cel mai mare număr de copii care pot fi implicați în serbare, știind ca fiecare dintre aceștia trebuie să relaționeze cu toți ceilalți copii din scenetă.

Date de intrare

Fișierul de intrare serbare2.in conţine n + 1 linii şi are structura:

Majoritatea copiilor sunt sociabili și relaționează ușor cu cei de vârsta lor dar sunt și copii mai timizi sau mai puțin atrași de activitățile de grup. În urma studierii comportamentului unui eșantion de n copii, s-a stabilit, pentru fiecare doi copii dacă relaționează sau nu. Pentru serbarea de sfârșit de an, s-a propus realizarea unei scenete și este necesară selectarea unei grupe cât mai numeroase de micuți dar fără a depăși k, numărul maxim de personaje. Rolurile presupun interacțiunea fiecărui copil selectat cu toți ceilalți mici actori care joacă în scenetă.

Cerința

Cunoscând n – dimensiunea eșantionului studiat, capacitatea fiecărui copil de a relaționa cu ceilalți și k – numărul maxim de personaje din scenetă, să se determine cel mai mare număr de copii care pot fi implicați în serbare, știind ca fiecare dintre aceștia trebuie să relaționeze cu toți ceilalți copii din scenetă.

Date de intrare

Fișierul de intrare serbare2.in conţine n + 1 linii şi are structura:
n k
a11 a12 ... a1n
a21 a22 ... a2n
...
an1 an2 ... ann

Unde n este dimensiunea eșantionului; k este numărul maxim de personaje
a[i,j] = 1, dacă copilul i relaționează cu copilul j sau
a[i,j] = 0, în caz contrar

Date de ieșire

Fișierul de ieșire serbare2.out conține o singură linie pe care se va scrie numărul maxim de copii care vor selectați pentru a juca în scenetă.

Restricții și precizări

• 2 ≤ n ≤ 100
• 2 ≤ k ≤ 10
• Se consideră că un copil NU relaționează cu el însuși.

Exemplul 1:

serbare2.in

3 3
0 1 1
1 0 1
1 1 0

serbare2.out

3

Exemplul 2:

serbare2.in

4 3
0 1 0 1
1 0 1 0
0 1 0 0
1 0 0 0

serbare2.out

2

#include <bits/stdc++.h>

using namespace std;

ifstream cin("serbare2.in");
ofstream cout("serbare2.out");

int n , k , p[20] , x[11] , a[101][101] , maxi;

int verifica(int p)
{
    for(int i = 1 ; i < p ; i++)
            if(a[x[i]][x[p]] == 0) return 0;
    return 1;
}

void back(int p)
{
    for(int i = x[p - 1] + 1 ; i <= n && maxi <= k; i++)
    {
        x[p] = i;
        if(verifica(p))
        {
            if(p > maxi) maxi = p;
            back(p + 1);
        }
    }
}

int main()
{
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++)
            cin >> a[i][j];
    back(1);
    cout << maxi;
}