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

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define SZ(x) int((x).size())
#define DBG(v) cerr << #v << " = " << (v) << endl;
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define fi first
#define se second

const int maxn = 200200;
int NODES, ID;

int N,M;
int res;


// Linie oznaczone [D], [M], [A], [L] potrzebne tylko, jeśli szukamy
//     numeracji [D]wuspójnych, [M]ostów, p.[A]rtykulacji, funkcji [L]ow
// mosty traktowane jako dwuspójne
struct Edge { // PRE: musi być bcc = -1 i bridge = 0 (konstruktor ustawia)
    Edge* rev;
    int id;
    int dest;
    int bcc;        // OUT: Numer komponentu
    bool bridge;    // OUT: Czy most                            // M
    Edge(int v) : dest(v), bcc(-1)
                  , bridge(0)                                   // M
    {};
};                 // IN: Liczba wierzchołków
list<Edge> adj[maxn];      // IN: Listy sąsiedztwa
int visit[maxn];
int bcc_num;   // OUT: Liczba komponentów                       // D
void add_edge (int a, int b) {
	//printf("dodaje krawedz %d %d\n", a, b);
	if (a==b) return;
   adj[a].pb(Edge(b));   adj[b].pb(Edge(a));
   adj[a].back().rev = &adj[b].back();
   adj[b].back().rev = &adj[a].back();
}
stack<Edge*> st;                                                // D
int dfsTime;
int bccDFS (int v, bool root = 0) {
    int lo = visit[v] = ++dfsTime;
    FOREACH(it,adj[v]) {
        if (it->bcc != -1) continue;
        st.push(&*it);                                          // D
        it->rev->bcc = -2;
        if (!visit[it->dest]) {
            int ulo = bccDFS(it->dest);
            lo = min(ulo, lo);
            it->bridge = it->rev->bridge = (ulo > visit[v]);    // M
            if (ulo >= visit[v]) {                              // AD
                Edge* edge;                                     // D
                do {                                            // D
                    edge = st.top(); st.pop();                  // D
                    edge->bcc = edge->rev->bcc = bcc_num;       // D
                } while (edge != &*it);                         // D
                ++bcc_num;                                      // D
            }                                                   // AD
        } else lo = min(lo, visit[it->dest]);
    }
    return lo;
}
void computeBCC(){
    fill(visit, visit+N+1, 0);
    dfsTime = 1;
    bcc_num = 0;                                                // D
    FOR(i,N) if(!visit[i]) bccDFS(i, 1); // byc moze zmienic FORI na FOR
}

void inedges() {
	int first = 1LL*M*ID/NODES;
	int last = 1LL*M*(ID+1)/NODES;
	REP(i,first,last-1) {
		int a = BridgeEndA(i);
		int b = BridgeEndB(i);
		//printf("krawedz nr %d\n", i);
		add_edge(a,b);
	}
}





vi bcc_occ[maxn];
void solve() {
	computeBCC();
	//printf("policzylem, mam %d dwuspojnych\n", bcc_num);
	FOR(i,bcc_num) bcc_occ[i].clear();
	FOR(i,N) FOREACH(it,adj[i]) {
		bcc_occ[it->bcc].pb(i);
	}
	FOR(i,N) adj[i].clear();
	FOR(i,bcc_num) {
		sort(bcc_occ[i].begin(), bcc_occ[i].end());
		int nn=bcc_occ[i].size();
		if (nn==1) continue;
		if (nn==2) {
			add_edge(bcc_occ[i][0], bcc_occ[i][1]);
			continue;
		}
		bcc_occ[i].pb(bcc_occ[i][0]);
		FOR(j,nn) if (bcc_occ[i][j] != bcc_occ[i][j+1]) add_edge(bcc_occ[i][j], bcc_occ[i][j+1]);
	}
}

const int MSGLIM = 19444;
void sendgraph(int who) {
	int counter = 0;
	//printf("wysylam do %d\n", who);
	FOR(i,N) {
		int k=0;
		FOREACH(j,adj[i]) if (i<j->dest) k++;
		if (counter == MSGLIM) {
			Send(who);
			counter = 0;
		}
		PutInt(who, k);
		counter++;
		FOREACH(j,adj[i]) if (i<j->dest) {
			if (counter == MSGLIM) {
				Send(who);
				counter = 0;
			}
			PutInt(who, j->dest);
			counter++;
			//printf("wysylam %d %d\n", i, j->dest);
		}
	}
	Send(who);
}





void getgraph(int who) {
	int counter = 0;
	//printf("odbieram od %d\n", who);
	Receive(who);
	FOR(i,N) {
		if (counter == MSGLIM) {
			Receive(who);
			counter = 0;
		}
		int k = GetInt(who);
		counter++;
		FOR(j,k) {
			if (counter == MSGLIM) {
				Receive(who);
				counter = 0;
			}
			int tt = GetInt(who);
			counter++;
			add_edge(i,tt);
		}
	}
}





void bridges() {
	computeBCC();
	FOR(i,N) FOREACH(it,adj[i]) if (it->bridge) res++;
}

void bruteforce() {
	FOR(i,N) adj[i].clear();
	FOR(i,M) {
		int a = BridgeEndA(i);
		int b = BridgeEndB(i);
		//printf("krawedz nr %d\n", i);
		add_edge(a,b);
	}
	computeBCC();
	FOR(i,N) FOREACH(it,adj[i]) if (it->bridge) {
		res++;
		printf("konce %d %d\n", i, it->dest);
	}
}

int main () {
	NODES = NumberOfNodes();
	ID = MyNodeId();
	N = NumberOfIsles();
	M = NumberOfBridges();
	inedges();
	solve();
	int numnodes = NODES;
	while (numnodes > 1) {
		int halfnum = (numnodes + 1) / 2;
		if (ID < halfnum) { // odbieram?
			if (ID+halfnum < numnodes) getgraph(ID+halfnum);
		} else { // wysylam
			sendgraph(ID-halfnum);
			return 0;
		}
		numnodes = halfnum;
		solve();
	}
	bridges();
	printf("%d\n", res/2);
	return 0;
	res=0;
	bruteforce();
	printf("%d\n", res/2);
}


/*
 [0 0] [3 6] [7 5] [3 5] [6 2] [9 1] [2 7] [0 9] [3 6] [0 6] [2 6] [1 8] [7 9] [2 0] [2 3] [7 5] [9 2] [2 8] [3 7] [9 6]
 [0 0] [3 6] [7 5] [3 5] [6 2] [9 1] [2 7] [0 9] [3 6] [0 6] [2 6] [1 8] [7 9] [2 0] [2 3] [7 5] [9 2] [2 8] [9 7] [3 6]
 */