#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>

#include "message.h"
#include "sabotaz.h"

using namespace std;

//#define DBG
//#define DBG_D
//#define SINGLE

char msg[1000];

#ifdef SINGLE
int NumberOfNodes() {return 1;}
int MyNodeId() {return 0;}
void PutInt(int target, int value) {}
void Send(int target) {}
int Receive(int source) {return 0;}
int GetInt(int source) {return 0;}

void write(char *msg) {printf(msg);}
#else
#if defined DBG || defined DBG_D
FILE *dbgf;
void write(char *msg) {
  fprintf(dbgf, msg);
  fflush(dbgf);
}
#endif
#endif // SINGLE


int n, m, nodes, node;
int master; // numer węzła nadrzędnego
vector<int> slaves; // numery węzłów podrzędnych
int m0, m1; // zakresy mostów dla instancji

///////////////////////////////////////////////////////////////////////////////

struct Wyspa {
  vector<int> mosty;
  bool odw;   // czy odwiedzony
  int nrg;    // numer dzielnicy głównej (spójnej składowej)
  int poz;    // liczba poziomów podpiętych wysp do Union-Find
  int pop;    // poprzednik w drzewie rozpinającym
  int ord;    // porządek odwiedzania w drzewie rozpinającym
  int nd;     // liczba potomków w drzewie rozpinającym (łącznie z daną wyspą)
};

Wyspa *MB; // MegaBajtopolis
int *low;  // najmniejszy i największy numer w porządku drzewa rozpinającego osiągalny z potomka
int *high; // krawędzią niedrzewową

int *gm;        // główne mosty użyte do wyznaczenia drzewa rozpinającego (krawędzie drzewowe)
int *gmA, *gmB; // numery łączonych wysp
int igm;        // ile jest danych w gm

#ifdef DBG
void dump()
{
  int i;
  for (i = 0; i < n; ++i) {
    sprintf(msg, "i=%d, nrg=%d, pop=%d, ord=%d, nd=%d, low=%d, high=%d\n", i, MB[i].nrg, MB[i].pop, MB[i].ord, MB[i].nd, low[i], high[i]); write(msg);
  }
}
#endif // DBG

////////////////////////////////////////////////////////////////////////////////////////////////////////////
// wysłanie tablicy dane do instancji pid (jeśli trzeba to w częściach po 60000 = 240k)
static const int chunk = 1995;
void nadaj(int pid, int *dane, int n)
{
  #ifdef DBG_D
  sprintf(msg, "### %d nadaje do %d (%d)\n", node, pid, n); write(msg);
  #endif // DBG
  PutInt(pid, n); // w pierwszym komunikacie dodatkowo długość całej paczki
  if (n == 0) {
    Send(pid);  // tylko info, że nic nie mamy do przesłania
    return;
  }
  int nchunks = (n - 1) / chunk + 1;
  for (int k = 0; k < nchunks; ++k) { // ile komunikatów
    for(int i = k * chunk; i < (k + 1) * chunk && i < n; ++i) PutInt(pid, dane[i]);
    Send(pid);
  }
}

int odbierz(int pid, int *dane)
{
  Receive(pid);
  #ifdef DBG_D
  sprintf(msg, "### %d odbiera od %d (%d)\n", node, pid, n); write(msg);
  #endif // DBG
  int n = GetInt(pid);
  if (n > 0) {
    int nchunks = (n - 1) / chunk + 1;
    for (int k = 0; k < nchunks; ++k) { // ile komunikatów
      if (k > 0) Receive(pid); // dla pierwszego nie trzeba bo było na początku
      for(int i = k * chunk; i < (k + 1) * chunk && i < n; ++i) dane[i] = GetInt(pid);
    }
  }
  return n;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////

int *buf;
int findW(int i)
{
  int ib = 0;
  while (MB[i].nrg != i) {
    buf[ib++] = i;
    i = MB[i].nrg;
  }
  for (int j = 0; j < ib; ++j) MB[buf[j]].nrg = i;
  return i;
}

bool unionW(int i, int j)  // przy okazji zwraca czy była potrzeba łączenia
{
  i = findW(i);
  j = findW(j);
  if (i == j)
    return false;
  else if (MB[i].poz > MB[j].poz)
    MB[j].nrg = i;
  else if (MB[i].poz < MB[j].poz)
    MB[i].nrg = j;
  else {
    MB[j].nrg = i;
    MB[i].poz++;
  }
  return true;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////
// tworzenie drzew rozpinających

//#define CZYTAJ_WSZ

#ifdef CZYTAJ_WSZ
set<pair<int, int> > wsz;
set<pair<int, int> > drz;
#endif // CZYTAJ_WSZ

void drzewo_rozp()
{
  int i;

  // zapisanie krawędzi
#ifdef CZYTAJ_WSZ
  for (i = 0; i < m; ++i) {
    int a = BridgeEndA(i);
    int b = BridgeEndB(i);
    if (a == b) continue;
    if (wsz.find(pair<int, int>(min(a, b), max(a, b))) != wsz.end()) continue;
    wsz.insert(pair<int, int>(min(a, b), max(a, b)));
#else
  for (i = 0; i < igm; ++i) {
    int a = gmA[i];
    int b = gmB[i];
#endif // CZYTAJ_WSZ
    MB[a].mosty.push_back(b);
    MB[b].mosty.push_back(a);
    #ifdef DBG
    sprintf(msg, "%d -- %d\n", a, b); write(msg);
    #endif // DBG
  }
  int ile_grup = 0;
  for (i = 0; i < n; ++i) if (!MB[i].odw) {
    #ifdef DBG
    sprintf(msg, "======\n"); write(msg);
    #endif // DBG
    ile_grup++;
    int ord = 0; // porządek odwiedzania
    stack<int> stos;
    stos.push(i);
    MB[i].odw = true;
    MB[i].pop = -1;       // wierzchołek drzewa
    while (stos.size()) {
      int k = stos.top();  // wyspa
      MB[k].ord = ord++;
      stos.pop();
      vector<int> &mosty = MB[k].mosty;
      #ifdef DBG
      //sprintf(msg, "k=%d, stos.size=%d mosty=%d\n", k, stos.size(), mosty.size()); write(msg);
      #endif // DBG
      for(int j = 0; j < mosty.size(); ++j) {
        int cel = mosty[j];
        if (!MB[cel].odw) {
          #ifdef DBG
          //sprintf(msg, "  -->%d\n", cel); write(msg);
          #endif // DBG
          MB[cel].odw = true;
          MB[cel].pop = k;
          stos.push(cel);
#ifdef CZYTAJ_WSZ
          drz.insert(pair<int, int>(min(k, cel), max(k, cel)));
#endif // CZYTAJ_WSZ
        }
      }
    }
  }
  #ifdef DBG_D
  sprintf(msg, "drzewo gotowe, grup=%d\n", ile_grup); write(msg);
  #ifdef CZYTAJ_WSZ
  sprintf(msg, "  drz.size=%d\n", drz.size()); write(msg);
  #endif
  #endif // DBG
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////
void obliczaj ()
{
  int i;
  set<int> drzewowe; // krawędzie drzewowe
#ifdef CZYTAJ_WSZ
  for (i = 0; i < m; ++i) {
    int a = BridgeEndA(i);
    int b = BridgeEndB(i);
    if (drz.find(pair<int, int>(min(a, b), max(a, b))) != drz.end()) drzewowe.insert(i);
  }
#else
  for (i = 0; i < igm; ++i) drzewowe.insert(gm[i]); // przerzuć drzewowe do seta
#endif // CZYTAJ_WSZ

  for (i = m0; i <= m1; ++i) {
    #ifdef DBG
    sprintf(msg, "i=%d\n", i); write(msg);
    #endif // DBG
    if (drzewowe.find(i) != drzewowe.end()) continue; // na tym etapie nie analizuj drzewowych
    int a = BridgeEndA(i);
    int b = BridgeEndB(i);
    if (a == b) continue; // ignoruj lokalne
    // aktualizuj high/low
    if (MB[a].ord > high[b]) high[b] = MB[a].ord;
    if (MB[b].ord > high[a]) high[a] = MB[b].ord;
    if (MB[a].ord < low[b])  low[b]  = MB[a].ord;
    if (MB[b].ord < low[a])  low[a]  = MB[b].ord;
  }
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////

int obliczaj_serwer()
{
  // oblicz nd, high, low: trzeba przechodzić po węzłach "od dołu" i poprawiać dane w poprzedniku
  int i, v;
  vector<pair<int, int> > kolejnosc;
  for (i = 0; i < n; ++i) {
    #ifdef DBG
    sprintf(msg, "i=%d\n", i); write(msg);
    #endif // DBG
    if (MB[i].ord > 0) {  // wierzchołek się zaktualizuje "od dołu"
      kolejnosc.push_back(pair<int, int>(MB[i].ord, i));   // (porządek, numer wyspy)
    }
  }
  sort(kolejnosc.begin(), kolejnosc.end());
  for (i = kolejnosc.size() - 1; i >= 0; --i) {  // teraz od tyłu
    #ifdef DBG
    sprintf(msg, "i=%d\n", i); write(msg);
    #endif // DBG
    v = kolejnosc[i].second;
    int pv = MB[v].pop; // poprzednik
    if (high[v] > high[pv]) high[pv] = high[v];
    if (low[v]  < low[pv])  low[pv]  = low[v];
    MB[pv].nd += MB[v].nd;
  }

  // teraz przejdź drzewowe i szukaj tych, które nie są w cyklach (bierz krawędź do poprzednika)
  int wynik = 0;
  int ile_drz = 0;
  for (v = 0; v < n; ++v) if (MB[v].ord > 0) {
    #ifdef DBG
    sprintf(msg, "v=%d\n", v); write(msg);
    #endif // DBG
    ile_drz++;
    int pv = MB[v].pop;
    if (low[v]  < MB[v].ord ||          // od v lub podrzędnego można wyjść niedrzewowo nad pv (lub do niego "dublem")
        high[v] >= MB[v].ord + MB[v].nd)  // od v lub podrzędnego można wyjść niedrzewowo gdzieś poza v i jego potomków
    {
      // cykl
    }
    else {
      #ifdef DBG
      sprintf(msg, "%d -- %d, low=%d, pv=%d, high=%d, v=%d, nd=%d\n", v, pv, low[v], MB[pv].ord, high[v], MB[v].ord, MB[v].nd); write(msg);
      #endif // DBG
      wynik++;  // krawędź drzewowa, która nie jest w cyklu
    }
  }
  #ifdef DBG_D
  sprintf(msg, "serwer obliczyl, ile_drz=%d\n", ile_drz); write(msg);
  #endif // DBG

  return wynik;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main()
{
  int i, j;
  #ifdef SINGLE
  LibInit();
  #endif // SINGLE

  n = NumberOfIsles();
  m = NumberOfBridges();
  node = MyNodeId();

  nodes = min(NumberOfNodes(), 1 + m / 100000); // ograniczenie liczby instancji aby każda miała min. 50-100k (lub całość dla n < 100k)
  if (node >= nodes) return 0; // niepotrzebna instancja

  #ifndef SINGLE
  #if defined DBG || defined DBG_D
  char fname[200];
  sprintf(fname, "node%02d.log", node);
  dbgf = fopen(fname, "w");
  #endif // defined
  #endif // SINGLE

  master = (node + 1) / 2 - 1;
  j = (node + 1) * 2 - 1; // pierwszy numer węzła podrzędnego
  for (i = 0; i <= 1 && i + j < nodes; ++i)
    slaves.push_back(j + i);

  int s = m / nodes;     // długość jednej sekcji
  m0 = node * s; // pozycja początkowa
  m1 = (node == nodes - 1 ? m - 1 : (node + 1) * s - 1); // pozycja końcowa

  #ifdef DBG
  sprintf(msg, "node=%d, n=%d, m=%d (%d..%d), slaves=%d\n", node, n, m, m0, m1, slaves.size());
  write(msg);
  #endif // DBG

  MB = new Wyspa[n];
  gm = new int[n];
  gmA = new int[n];
  gmB = new int[n];
  buf = new int[n];
  low = new int[n];
  high = new int[n];

  for (i = 0; i < n; ++i) {
    MB[i].odw = false;
    MB[i].nrg = i; // na początek każda wyspa jest samotna
    MB[i].poz = 0;
    low[i] = n + 1;  // na razie nie ma osiągalnych niedrzewowymi, +1 na zapas :-)
    high[i] = -1;
    MB[i].nd = 1;   // sam jak palec
  }

  // wczytanie danych
  igm = 0;
  for (i = m0; i <= m1; ++i) {
    int a = BridgeEndA(i);
    int b = BridgeEndB(i);
    #ifdef DBG
    //sprintf(msg, "i=%d, a=%d, b=%d\n", i, a, b); write(msg);
    #endif // DBG
    if (a != b)  // ignoruj lokalne
      if (unionW(a, b)) {
        gm[igm] = i;  // numer krawędzi rozpinającej
        gmA[igm] = a;
        gmB[igm] = b;
        igm++;
      }
  }

  #ifdef DBG_D
  set<int> grupy;
  for (i = 0; i < n; ++i)
    grupy.insert(findW(i));
  sprintf(msg, "wczytane n=%d, grup=%d igm=%d\n", n, grupy.size(), igm);
  write(msg);
  #endif // DBG

  // -----------------------------------------------------------------------------------------------
  // scal dane od podrzędnych instancji
  int *sgm = new int[n];
  int isgm;
  for (int sl = 0; sl < slaves.size(); ++sl) {
    isgm = odbierz(slaves[sl], sgm);
    #ifdef DBG_D
    sprintf(msg, "odebrane od %d\n", slaves[sl]); write(msg);
    #endif // DBG
    for (i = 0; i < isgm; ++i) {
      int a = BridgeEndA(sgm[i]);
      int b = BridgeEndB(sgm[i]);
      if (a != b)  // ignoruj lokalne
        if (unionW(a, b)) {
          gm[igm] = sgm[i];  // numer krawędzi użytej do połączenia dzielnic
          gmA[igm] = a;
          gmB[igm] = b;
          igm++;
        }
    }
  }
  if (node > 0) { // wysłanie do mastera i odebranie finalnej listy krawędzi rozpinających
    nadaj(master, gm, igm);
    #ifdef DBG_D
    sprintf(msg, "gm wyslane do mastera %d\n", master); write(msg);
    #endif // DBG
    igm = odbierz(master, gm);
    #ifdef DBG_D
    sprintf(msg, "gm odebrane od mastera %d\n", master); write(msg);
    #endif // DBG
  }
  for (int sl = 0; sl < slaves.size(); ++sl) {  // rozesłanie do podrzędnych
    nadaj(slaves[sl], gm, igm);
    #ifdef DBG_D
    sprintf(msg, "gm nadane do %d\n", slaves[sl]); write(msg);
    #endif // DBG
  }

  // -----------------------------------------------------------------------------------------------
  #ifdef DBG
  sprintf(msg, "start obliczen\n");
  write(msg);
  #endif // DBG
  drzewo_rozp();
  obliczaj();
  #ifdef DBG
  sprintf(msg, "obliczone\n"); write(msg);
  #endif // DBG
  // -----------------------------------------------------------------------------------------------
  // scal high/low podrzędnych instancji
  int *shi = new int[n];
  int *slo = new int[n];

  for (int sl = 0; sl < slaves.size(); ++sl) {
    odbierz(slaves[sl], shi); // wiadomo, że odbieram n
    odbierz(slaves[sl], slo);
    #ifdef DBG_D
    sprintf(msg, "lo/hi odebrane od %d\n", slaves[sl]); write(msg);
    #endif // DBG
    for (i = 0; i < n; ++i) {
      if (shi[i] > high[i]) high[i] = shi[i];
      if (slo[i] < low[i])  low[i]  = slo[i];
    }
  }
  if (node > 0) { // wysłanie do mastera
    nadaj(master, high, n);
    nadaj(master, low, n);
    #ifdef DBG_D
    sprintf(msg, "lo/hi nadane do mastera\n"); write(msg);
    #endif // DBG
  }

  // -----------------------------------------------------------------------------------------------
  if (node == 0) {
    int wynik = obliczaj_serwer();
    printf("%d\n", wynik);
    #ifdef DBG
    dump();
    sprintf(msg, "wynik=%d\n", wynik); write(msg);
    #endif // DBG
  }
  #ifdef DBG
  else
    dump();
  #endif // DBG
}