7.A Dodatak: pretraga sa povratkom

7.A.1 Primeri pretrage sa povratkom

Zadatak: Bojenje grafa sa tri boje

U jednoj zemlji postoji nekoliko planinskih vrhova na kojima će se postaviti predajnici najsavremenije mobilne mreže. Oni mogu da rade na jednoj od tri različite radio-frekvencije. Svaki predajnik može da prenosi specijalni signal drugim predajnicima koji su blizu njega, pri čemu dva predajnika koji su blizu jedan drugome ne smeju da koriste istu frekvenciju. Napisati program koji određuje da li je moguće dodeliti frekvencije svim predajnicima tako da nema sudaranja.

Opis ulaza

Sa standardnog ulaza se učitava broj predajnika \(n\) (\(1 \leq n \leq 100\)), a nakon toga broj parova bliskih predajnika \(m\) (\(n-1 \leq m \leq \frac{n(n-1)}{2}\)). Nakon toga, u narednih \(m\) redova se učitavaju parovi bliskih predajnika (svi predajnici su obeleženi brojevima od \(0\) do \(n-1\)). Sistem je građen tako da se signal sigurno može preneti od bilo kog do bilo kog drugog predajnika.

Opis izlaza

Na standardni izlaz ispisati oznake frekvencija (1, 2 i 3) koje su redom dodeljene predajnicima ili - ako frekvencije nije moguće dodeliti tako da se bliski predajnici ne sudaraju. Ako je frekvencije moguće dodeliti na više načina, ispisati onaj koji je najmanji u leksikografskom redosledu.

Primer

Ulaz

5
5
0 1
0 4
1 2
1 4
2 3
2 4
3 4

Izlaz

1 2 1 2 3

Rešenje

Ovaj problem je u literaturi poznat kao problem 3-bojenja grafova (svaki predajnik predstavlja čvor grafa, a svaka frekvencija jednu od 3 dopuštene boje).

Zadatak se jednostavno (ali ne i efikasno) rešava bektreking pretragom.

Primetimo da je problem simetričan i da ako se prvom čvoru može dodeliti neka boja, oznake boja se mogu promeniti tako da se tom prvom čvoru dodeli bilo koja druga boja. Stoga možemo pretpostaviti da je prvi čvor obojen bojom 1 (jer se traži najmanji raspored boja po leksikografskom poretku). Ni jedan od njegovih suseda (a oni sigurno postoje, jer je graf povezan) ne može biti obojen bojom 1. Pošto se traži najmanji raspored boja leksikografskom poretku, njegov sused koji ima najmanji redni broj treba da bude obojen bojom \(2\). Za ostale čvorove pokušavamo bojenje raznim bojama.

Primer 7.A.1. Na slikama je prikazan primer postupka bojenja grafa sa tri boje. Pre početka pretrage čvor 0 se boji u crveno, a čvor 1 (najmanji sused čvora 0) u zeleno. Tada čvor 2 mora da se oboji u plavo. Ako se čvor 3 oboji prvom raspoloživom bojom (crvenom), tada čvor 4 mora da se oboji u plavo i čvor 5 ne može da se oboji (jer je susedan i sa crvenim i sa zelenim i sa plavim čvorom). Tada se pretraga vraća unatrag i čvor 3 boji u narednu raspoloživu boju – zelenu. Čvor 4 se boji u prvu raspoloživu boju – crvenu, nakon čega čvor 5 mora da se oboji u plavu. U tom trenutku je ceo graf uspešno obojen sa tri boje.

// funkcija boji dati cvor, pri cemu su zadati
// susedi svih cvorova i boje do sada obojenih cvorova
bool oboj(const vector<vector<int>>& susedi, int cvor,
          vector<int>& boje) {
  // ako su svi cvorovi obojeni, bojenje sa 3 boje je uspesno
  int brojCvorova = susedi.size();
  if (cvor >= brojCvorova)
    return true;

  // ako je cvor vec obojen, preskacemo ga
  if (boje[cvor] != 0)
    return oboj(susedi, cvor + 1, boje);

  // pokusavamo da cvoru dodelimo svaku od 3 raspolozive boje
  for (int boja = 1; boja <= 3; boja++) {
    // linearnom pretragom proveravamo da li je moguce obojiti
    // cvor u tekucu boju
    bool mozeBoja = true;
    // proveravamo sve susede
    for (int sused : susedi[cvor])
      // ako je neki od njih vec obojen u tekucu boju
      if (boje[sused] == boja) {
        // bojenje nije moguce
        mozeBoja = false;
        break;
      }
    if (mozeBoja) {
      // bojimo tekuci cvor
      boje[cvor] = boja;
      // pokusavamo rekurzivno bojenje narednog cvora i ako
      // uspemo, tada je bojenje moguce
      if (oboj(susedi, cvor+1, boje))
        return true;
      // ponistavamo boju tekuceg cvora
      boje[cvor] = 0;
    }
  }

  // probali smo sve tri boje i ni jedno bojenje nije moguce
  return false;
}

bool oboj(const vector<vector<int>>& susedi, vector<int>& boje) {
  // broj cvorova grafa
  // prva cvor 0 i njegov prvi sused se boje u boje 1 i 2
  boje[0] = 1; boje[*min_element(begin(susedi[0]),
                                 end(susedi[0]))] = 2;
  // krecemo bojenje od cvora 0
  return oboj(susedi, 0, boje);
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// funkcija boji dati cvor, pri cemu su zadati
// susedi svih cvorova i boje do sada obojenih cvorova
bool oboj(const vector<vector<int>>& susedi, int cvor,
          vector<int>& boje) {
  // ako su svi cvorovi obojeni, bojenje sa 3 boje je uspesno
  int brojCvorova = susedi.size();
  if (cvor >= brojCvorova)
    return true;

  // ako je cvor vec obojen, preskacemo ga
  if (boje[cvor] != 0)
    return oboj(susedi, cvor + 1, boje);

  // pokusavamo da cvoru dodelimo svaku od 3 raspolozive boje
  for (int boja = 1; boja <= 3; boja++) {
    // linearnom pretragom proveravamo da li je moguce obojiti
    // cvor u tekucu boju
    bool mozeBoja = true;
    // proveravamo sve susede
    for (int sused : susedi[cvor])
      // ako je neki od njih vec obojen u tekucu boju
      if (boje[sused] == boja) {
        // bojenje nije moguce
        mozeBoja = false;
        break;
      }
    if (mozeBoja) {
      // bojimo tekuci cvor
      boje[cvor] = boja;
      // pokusavamo rekurzivno bojenje narednog cvora i ako
      // uspemo, tada je bojenje moguce
      if (oboj(susedi, cvor+1, boje))
        return true;
      // ponistavamo boju tekuceg cvora
      boje[cvor] = 0;
    }
  }

  // probali smo sve tri boje i ni jedno bojenje nije moguce
  return false;
}

bool oboj(const vector<vector<int>>& susedi, vector<int>& boje) {
  // broj cvorova grafa
  // prva cvor 0 i njegov prvi sused se boje u boje 1 i 2
  boje[0] = 1; boje[*min_element(begin(susedi[0]),
                                 end(susedi[0]))] = 2;
  // krecemo bojenje od cvora 0
  return oboj(susedi, 0, boje);
}

int main() {
  // broj cvorova
  int n;
  cin >> n;
  // broj grana
  int m;
  cin >> m;
  vector<vector<int>> susedi(n);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    susedi[a].push_back(b);
    susedi[b].push_back(a);
  }

  vector<int> boje(n, 0);
  if (oboj(susedi, boje)) {
    for (int b : boje)
      cout << b << " ";
    cout << endl;
  } else {
    cout << "-" << endl;
  }
  
  return 0;
}

Zadatak: Sudoku

Napisati program koji popunjava Sudoku zagonetku čiji je cilj da se u matricu dimenzije 9 puta 9 rasporede brojevi od 1 do 9, tako da u svakoj vrsti, u svakoj koloni i u svakom od 9 kvadrata dimenzije 3 puta 3 svi brojevi različiti.

Opis ulaza

Sa standardnog ulaza se učitava matrica dimenzije 9 puta 9 u kojoj su već upisani neki brojevi, a na poljima koja su prazna upisana je nula.

Opis izlaza

Na standardni izlaz ispisati rešenje zagonetke (test-primeri će biti takvi da je rešenje sigurno jedinstveno).

Primer

Ulaz

749030680
006508000
000760324
800057060
407000508
050980002
184076000
000403800
063010247

Izlaz

749132685
326548179
518769324
892357461
437621598
651984732
184276953
275493816
963815247

Rešenje

Zadatak rešavamo bektrekingom tj. rekurzivno implementiranom pretragom u dubinu. Rekruzivna funkcija uz matricu koja se popunjava dobija i redni broj polja koje treba popuniti (ona vraća informaciju o tome da li je matricu bilo moguće potpuno popuniti). Popunjavanje kreće od gornjeg levog ugla i teče vrstu po vrstu, sve dok ne popunimo celu matricu. Koordinate polja se veoma jednostavno mogu odrediti na osnovu njegovog rednog broja. Ako je trenutno polje već popunjeno (jer su u startu neka polja već popunjena), tada odmah prelazimo na naredno polje. U suprotnom proveravamo sve moguće vrednosti za to polje. Nakon upisa vrednosti proveravamo da li je time napravljen neki konflikt tj. da li se desilo da je u istoj vrsti, u istoj koloni ili u istom kvadratu već postojao broj koji je upisan. Ako jeste, pretragu prekidamo, a ako nije, nastavljamo je dalje, popunjavanjem narednog polja. Čim neki od rekurzivnih poziva uspe da popuni celu matricu, pretraga se prekida i naredni rekurzivni pozivi se ne vrše.

const int n = 3;

bool konflikt(const vector<vector<int>>& A, int i, int j) {
  // da li se A[i][j] nalazi već u koloni j
  for (int k = 0; k < n * n; k++)
    if (k != i && A[i][j] == A[k][j])
      return true;
  
  // da li se A[i][j] nalazi već u vrsti i
  for (int k = 0; k < n * n; k++)
    if (k != j && A[i][j] == A[i][k])
      return true;

  // da li se A[i][j] već nalazi u kvadratu koji sadrži
  // polje (i, j)
  int x = i / n, y = j / n;
  for (int k = x * n; k < (x + 1) * n; k++)
    for (int l = y * n; l < (y + 1) * n; l++)
      if ((k != i || l != j) && A[i][j] == A[k][l])
        return true;

  // ne postoji konflikt
  return false;
}

bool sudoku(vector<vector<int>>& A, int rbr) {
  int i = rbr / (n*n), j = rbr % (n*n);
  // ako je polje (i, j) već popunjeno
  if (A[i][j] != 0) {
    // ako je u pitanju poslednje polje, uspešno smo popunili
    // ceo sudoku
    if (rbr == n * n * n * n - 1)
      return true;
    // rekurzivno nastavljamo sa popunjavanjem
    return sudoku(A, rbr + 1);
  } else {
    // razmatramo sve moguće vrednosti koje možemo da upišemo
    // na polje (i, j)
    for (int k = 1; k <= n*n; k++) {
      // upisujeAo vrednost k
      A[i][j] = k;
      // ako time napravljen neki konflikt, nastavljamo
      // popunjavanje (pošto je polje popunjeno, na sledeće
      // polje će se automatski preći u rekurzivnom pozivu)
      // ako se sudoku uspešno popuni, prekidaAo pretragu
      if (!konflikt(A, i, j))
        if (sudoku(A, rbr))
          return true;
    }
    // poništavamo vrednost upisanu na polje (i, j), jer se
    // popunjena polja smatraju fiksiranim
    // (datim u postavci problema)
    A[i][j] = 0;
    // konstatujemo da ne postoji rešenje
    return false;
  }
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int n = 3;

bool konflikt(const vector<vector<int>>& A, int i, int j) {
  // da li se A[i][j] nalazi već u koloni j
  for (int k = 0; k < n * n; k++)
    if (k != i && A[i][j] == A[k][j])
      return true;
  
  // da li se A[i][j] nalazi već u vrsti i
  for (int k = 0; k < n * n; k++)
    if (k != j && A[i][j] == A[i][k])
      return true;

  // da li se A[i][j] već nalazi u kvadratu koji sadrži
  // polje (i, j)
  int x = i / n, y = j / n;
  for (int k = x * n; k < (x + 1) * n; k++)
    for (int l = y * n; l < (y + 1) * n; l++)
      if ((k != i || l != j) && A[i][j] == A[k][l])
        return true;

  // ne postoji konflikt
  return false;
}

bool sudoku(vector<vector<int>>& A, int rbr) {
  int i = rbr / (n*n), j = rbr % (n*n);
  // ako je polje (i, j) već popunjeno
  if (A[i][j] != 0) {
    // ako je u pitanju poslednje polje, uspešno smo popunili
    // ceo sudoku
    if (rbr == n * n * n * n - 1)
      return true;
    // rekurzivno nastavljamo sa popunjavanjem
    return sudoku(A, rbr + 1);
  } else {
    // razmatramo sve moguće vrednosti koje možemo da upišemo
    // na polje (i, j)
    for (int k = 1; k <= n*n; k++) {
      // upisujeAo vrednost k
      A[i][j] = k;
      // ako time napravljen neki konflikt, nastavljamo
      // popunjavanje (pošto je polje popunjeno, na sledeće
      // polje će se automatski preći u rekurzivnom pozivu)
      // ako se sudoku uspešno popuni, prekidaAo pretragu
      if (!konflikt(A, i, j))
        if (sudoku(A, rbr))
          return true;
    }
    // poništavamo vrednost upisanu na polje (i, j), jer se
    // popunjena polja smatraju fiksiranim
    // (datim u postavci problema)
    A[i][j] = 0;
    // konstatujemo da ne postoji rešenje
    return false;
  }
}

int main() {
  vector<vector<int>> A(n * n);
  for (int i = 0; i < n * n; i++) {
    A[i].resize(n * n);
    string s;
    getline(cin, s);
    for (int j = 0; j < n * n; j++)
      A[i][j] = s[j] - '0';
  }

  if (!sudoku(A, 0))
    cout << "nema" << endl;
  else {
    for (int i = 0; i < n*n; i++) {
      for (int j = 0; j < n*n; j++)
        cout << A[i][j];
      cout << endl;
    }
  }

  return 0;
}

7.A.2 Grananje sa ograničavanjem

Tehnika grananja sa ograničavanjem (engl. branch and bound) je metoda za rešavanje optimizacionih problema koja sistematski istražuje prostor mogućih rešenja grananjem (engl. branch), odnosno deljenjem problema na manje potprobleme. Istovremeno, koristi se i ograničenje (engl. bound) – procena najboljeg mogućeg rešenja u datom potprostoru – kako bi se eliminisali potprostori koji ne mogu dati bolje rešenje od već pronađenih. Na taj način se izbegava nepotrebno pretraživanje i ubrzava pronalaženje optimalnog rešenja. Dakle, već pronađene vrednosti rešenja u jednom delu prostora pretrage se koriste kao ograničenja u narednim delovima prostora pretrage. Ilustrujmo ovu tehniku na problemu pronalaženja najmanjeg broja boja potrebnih da se oboji graf tako da su svi susedni čvorovi obojeni različitim bojama.

Zadatak: K bojenje

Potrebno je rasporediti promenljive u registre procesora. Pri tom, je poznato da neke promenljive ne smeju da budu smeštene u isti registar (jer se koriste istovremeno). Napisati program koji određuje najmanji broj registara potreban da se smeste sve promenljive. Na primer, u kodu

x = a + b;
y = x * b;
return y;

Promenljive a i b kao i promenljive x i b ne smeju biti smeštene u isti registar. Moguće je upotrebiti samo dva registra. Prvo se u registar 1 smešta promenljiva a, a u registar 2 promenljiva b. Nakon toga se vrednost promenljive x smešta u registar 1 (jer vrednost promenljive a nije nadalje potrebna). Nakon toga se vrednost promenljive y može smestiti bilo u registar 1, bilo u registar 2, jer nadalje nisu potrebni ni vrednost promenljive x ni vrednost promenljive b.

Opis ulaza

Sa standardnog ulaza se unosi broj promenljivih \(n\) (\(1 \leq n \leq 50\)). Nakon toga se do kraja ulaza unose parovi promenljivih koje ne smeju da se smeste u iste registre (promenljive se broje od \(0\) do \(n-1\)).

Opis izlaza

Na standardni izlaz ispisati najmanji broj registara potrebnih da se sve promenljive smeste.

Primer

Ulaz

6
0 1
0 2
1 2
1 4
1 5
2 3
3 4
3 5
4 5

Izlaz

3

Rešenje

Promenljive možemo predstaviti čvorovima grafa tako da grane postoje između promenljivih koje ne smeju biti obojene istom bojom, dok registre možemo predstaviti bojama čvorova grafa. Time se polazni problem svodi na određivanje najmanjeg broja boja potrebnog da se oboje čvorovi grafa tako da nikoja dva susedna čvora nisu obojena istom bojom. Jednostavnosti radi pretpostavićemo da je graf sačinjen od promenljivih i od ograničenja između njih povezan.

Zadatak je moguće rešiti korišćenjem funkcije koja proverava da li se bojenje može izvršiti pomoću \(k\) boja i primenom binarne pretrage za određivanje prelomne tačke, tj. najmanje vrednosti \(k\) takve da se graf može obojiti sa \(k\) boja. Provera da li se graf može obojiti sa \(k\) boja može se izvršiti bektreking pretragom.

Zadatak se može rešiti i samo jednom bektreking pretragom. Za razliku od provere da li se graf može obojiti sa \(k\) boja, koja se može zaustaviti čim se naiđe na prvo uspešno bojenje, u ovom algoritmu (za određivanje najmanjeg dovoljnog broja boja) potrebno je obići celo stablo pretrage. Kada se pronađe neko uspešno bojenje sa određenim brojem boja (recimo \(k\)), prilikom povratka u pretrazi vrši se ograničavanje boja čvorova na vrednosti od \(1\) do \(k-1\) (jer nam je cilj da pokušamo da pronađemo bojenje sa manjim brojem boja od \(k\)). Početno ogrančenje broja boja je \(n\), jer smo sigurni da se graf sa \(n\) čvorova može obojiti pomoću \(n\) boja.

Primer 7.A.2.

Na slici je prikazano bojenje grafa sa najmanjim brojem boja. Pretpostavimo da su boje obeležene brojevima od 1 do \(n\). Bez gubitka na opštosti se može pretpostaviti da se čvor 0 može obojiti u boju broj 1 (crvenu), a njegov prvi sused, čvor 1, u boju broj 2 (zelenu). Za čvor 2 su nam inicijalno na raspolaganju boje od 1 do 6 (jer graf ima 6 čvorova). Bojenje u boje 1 i 2 nije moguće, pa se čvor 2 boji u boju broj 3 (plavu). Za čvor 3 i dalje su moguće sve boje od 1 do 6, pa se on boji u prvu raspoloživu boju tj. boju 1 (crvenu). Za čvor 4 su raspoložive boje od 1 do 6, pa sa i on boji u prvu raspoloživu boju tj. boju 3 (plavu). Na kraju, i za čvor 5 su raspoložive boje od 1 do 6 i on se boji u prvu raspoloživu boju tj. boju 4. U tom trenutku smo pronašli bojenje sa 4 boje i pošto u nastavku pretrage tražimo samo bolja rešenja, raspoložive će biti samo prve tri boje (1, 2 i 3). Vraćamo se na čvor 4 i njegovu boju ne možemo da promenimo (jer već ima najveću raspoloživu boju). Zato se vraćamo na čvor 3. Njegovu boju možemo da promenimo u boju 2 (zelenu). Tada čvor 4 bojimo u prvu raspoloživu boju 1 (crvenu), a čvor 5 u boju 3 (plavu), jer boje 1 i 2 nisu moguće, a na raspolaganju su nam boje od 1 do 3. U tom trenutku je pronađeno uspešno bojenje sa 3 boje i razmatramo samo bojenja sa 2 boje (kandidati za boje su sada samo 1 i 2). Pošto su na putu do čvora 4 već upotrebljene tri boje, vraćamo se unazad, bez razmatranja daljih mogućnosti promene boje konkretnog čvora sve do čvora 2. Pošto čvor 2 ne može da promeni boju (jer je već obojen u boju 3, a na raspolaganju su nam sada samo boje 1 i 2), vraćamo se na čvorove 1 i 0 koji imaju fiksirane boje i pretraga se završava.

// poznato je da se graf moze obojiti sa ovim brojem boja
// jednostavnosti radi koristimo globalnu promenljivu (mada to
// nije neohpodno)
int brojBoja;

// funkcija pokusava da prosiri bojenje graf dato nizom boje,
// u kome je trenutno upotrebljen broj boja dat promenljivom
// upotrebljenoBoja, tako sto boji dati cvor, koristeci
// raspolozive boje, koje su odredjene globalnom promenljivom
// brojBoja
void oboj(const vector<vector<int>>& susedi, 
          int cvor, vector<int>& boje, int upotrebljenoBoja) {
  // ako su svi cvorovi obojeni, bojenje je uspesno
  int brojCvorova = susedi.size();
  if (cvor >= brojCvorova) {
    brojBoja = upotrebljenoBoja;
    return;
  }

  // ako je cvor vec obojen, preskacemo ga
  if (boje[cvor] != 0) {
    oboj(susedi, cvor + 1, boje, upotrebljenoBoja);    
    return;
  }
  
  // pokusavamo da cvoru dodelimo svaku od raspolozivih boja
  for (int boja = 1; boja < brojBoja; boja++) {
    // linearnom pretragom proveravamo da li je moguce obojiti
    // cvor u tekucu boju
    bool mozeBoja = true;
    // proveravamo sve susede
    for (int sused : susedi[cvor])
      // ako je neki od njih vec obojen u tekucu boju
      if (boje[sused] == boja) {
        // bojenje nije moguce
        mozeBoja = false;
        break;
      }
    if (mozeBoja) {
      // bojimo tekuci cvor
      boje[cvor] = boja;
      // pokusavamo rekurzivno bojenje narednog cvora i ako
      // uspemo tada je bojenje moguce
      oboj(susedi, cvor+1, boje, max(upotrebljenoBoja, boja));
      boje[cvor] = 0;

      // ako smo vec upotrebili previse boja, mozemo odmah
      // preseci pretragu
      if (upotrebljenoBoja >= brojBoja)
        return;
    }
  }
}

// najmanji broj boja kojima se mogu obojiti cvorovi grafa,
// tako da nikoja dva cvora nisu susedna
int minBrojBoja(const vector<vector<int>>& susedi) {
  // broj cvorova grafa
  int n = susedi.size();
  // boja svakog cvora
  vector<int> boje(n, 0);
  // graf se sigurno moze obojiti sa n boja
  brojBoja = n;
  // prva cvor 0 i njegov prvi sused se boje u boje 0 i 1
  boje[0] = 1; boje[susedi[0][0]] = 2;
  // krecemo bojenje od cvora 0
  oboj(susedi, 0, boje, 2);
  return brojBoja;
}

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

// poznato je da se graf moze obojiti sa ovim brojem boja
// jednostavnosti radi koristimo globalnu promenljivu (mada to
// nije neohpodno)
int brojBoja;

// funkcija pokusava da prosiri bojenje graf dato nizom boje,
// u kome je trenutno upotrebljen broj boja dat promenljivom
// upotrebljenoBoja, tako sto boji dati cvor, koristeci
// raspolozive boje, koje su odredjene globalnom promenljivom
// brojBoja
void oboj(const vector<vector<int>>& susedi, 
          int cvor, vector<int>& boje, int upotrebljenoBoja) {
  // ako su svi cvorovi obojeni, bojenje je uspesno
  int brojCvorova = susedi.size();
  if (cvor >= brojCvorova) {
    brojBoja = upotrebljenoBoja;
    return;
  }

  // ako je cvor vec obojen, preskacemo ga
  if (boje[cvor] != 0) {
    oboj(susedi, cvor + 1, boje, upotrebljenoBoja);    
    return;
  }
  
  // pokusavamo da cvoru dodelimo svaku od raspolozivih boja
  for (int boja = 1; boja < brojBoja; boja++) {
    // linearnom pretragom proveravamo da li je moguce obojiti
    // cvor u tekucu boju
    bool mozeBoja = true;
    // proveravamo sve susede
    for (int sused : susedi[cvor])
      // ako je neki od njih vec obojen u tekucu boju
      if (boje[sused] == boja) {
        // bojenje nije moguce
        mozeBoja = false;
        break;
      }
    if (mozeBoja) {
      // bojimo tekuci cvor
      boje[cvor] = boja;
      // pokusavamo rekurzivno bojenje narednog cvora i ako
      // uspemo tada je bojenje moguce
      oboj(susedi, cvor+1, boje, max(upotrebljenoBoja, boja));
      boje[cvor] = 0;

      // ako smo vec upotrebili previse boja, mozemo odmah
      // preseci pretragu
      if (upotrebljenoBoja >= brojBoja)
        return;
    }
  }
}

// najmanji broj boja kojima se mogu obojiti cvorovi grafa,
// tako da nikoja dva cvora nisu susedna
int minBrojBoja(const vector<vector<int>>& susedi) {
  // broj cvorova grafa
  int n = susedi.size();
  // boja svakog cvora
  vector<int> boje(n, 0);
  // graf se sigurno moze obojiti sa n boja
  brojBoja = n;
  // prva cvor 0 i njegov prvi sused se boje u boje 0 i 1
  boje[0] = 1; boje[susedi[0][0]] = 2;
  // krecemo bojenje od cvora 0
  oboj(susedi, 0, boje, 2);
  return brojBoja;
}

int main() {
  // broj cvorova
  int n;
  cin >> n;
  // liste suseda svakog cvora
  vector<vector<int>> susedi(n);
  
  // ucitavamo grane grafa
  int a, b;
  while (cin >> a >> b) {
    susedi[a].push_back(b);
    susedi[b].push_back(a);
  }
  
  // pronalazimo i ispisujemo najmanji broj boja kojima se graf moze
  // obojiti tako da nikoja dva cvora nisu susedna
  cout << minBrojBoja(susedi) << endl;
  
  return 0;
}