//Jakub Staro�
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <functional>
#include <memory>

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

#define DEBUG_MODE

using namespace std;

typedef char int8;
typedef unsigned char uint8;
typedef short int int16;
typedef unsigned short int uint16;
typedef int int32;
typedef unsigned int uint32;
typedef long long int64;
typedef unsigned long long uint64;

typedef std::pair<int32,int32> int32_pair;
typedef std::pair<uint32, uint32> uint32_pair;
typedef std::pair<int64,int64> int64_pair;
typedef std::pair<uint64,uint64> uint64_pair;

typedef std::vector<bool> bit_vector;

#ifdef DEBUG_MODE
#define debug_print(x) cerr << #x << " = " << x << endl
#define print_line cerr << "Line " << __LINE__ << endl
#include <cassert>
#else
#define debug_print(x)
#define print_line
#define assert(x)
#endif

#define rep(i, x) for(int32 i = 0 ; i < (x) ; i++)
#define for_range(i, begin, end) for(auto i = (begin) ; i != (end) ; ++i )
#define all(c) (c).begin(),(c).end()
#define sort_all(x) sort( all(x) )
#define divide(a, b) ( ( (b)%(a) ) == 0 )
#define mp(x, y) make_pair(x,y)
#define pb(x) push_back(x)

#define sig(x) ( (x) == 0 ? 0 : ( (x) < 0 ? -1 : 1 ) )

const double epsilon = 1e-5;

template<class T>
void unique(std::vector<T>& v) {
	sort_all(v);
	v.resize( std::unique(all(v)) - v.begin() );
}

ostream& newline(ostream& str) {
	str.put('\n');
	return str;
}

template<typename T1, typename T2>
istream& operator>>(istream& stream, std::pair<T1, T2>& pair) {
	stream >> pair.first >> pair.second;
	return stream;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& stream, const std::pair<T1, T2>& pair) {
#ifdef DEBUG_MODE
	stream << "(" << pair.first << ", " << pair.second << ")";
#else
	stream << pair.first << ' ' << pair.second;
#endif
	return stream;
}

template<class T>
ostream& operator<<(ostream& str, const vector<T>& v) {
	if(!v.empty())	{
		for(int32 i = 0 ; i + 1 < v.size() ; i++)		
			str << v[i] << ' ';		
		str << v.back();
	}
	return str;
}

uint64_pair GetRange(uint64 length, uint64 index, uint64 max) {
	uint64 partLength = (length + max - 1) / max;
	uint64 begin = min(index * partLength, length);
	uint64 end = min((index + 1) * partLength, length);

	return uint64_pair(begin, end);
}

typedef pair<uint32_pair, uint32> edge_type;

class Graf {
 public:
	typedef vector<uint32_pair> list_type;

	Graf() {

	}

	Graf(uint32 n) {
		resize(n);
	}

	void resize(uint32 k) {
		graf.resize(k);
	}

	void add(uint32 a, uint32 b, uint32 id) {
		graf[a].emplace_back(b, id);
		graf[b].emplace_back(a, id);
		edges.emplace_back(uint32_pair(a, b), id);
	}

	uint32 deg(uint32 k) {
		return graf[k].size();
	}

	list_type& obok(uint32 k) {
		return graf[k];
	}

	uint32 size() {
		return graf.size();
	}

	const vector<edge_type>& getAllEdges() {
		return edges;
	}

 private:
	vector<list_type> graf;
	vector<edge_type> edges;
};

class BridgeFinder {
 public:
	BridgeFinder(Graf& graf_) : graf(graf_) {
		graph_size = graf.size();
		time = 0;
	}

	void bridgeUtil(int32 u)
	{
		visited[u] = true;
		disc[u] = low[u] = ++time;

		for (uint32_pair vv : graf.obok(u))
		{
			uint32 v = vv.first;
			if (!visited[v])
			{
				parent[v] = u;
				bridgeUtil(v);
				low[u]  = min(low[u], low[v]);
				if (low[v] > disc[u])
					bridges.push_back(vv.second);
			}

			else if (v != parent[u])
				low[u]  = min(low[u], disc[v]);
		}
	}

	void bridge()
	{
		visited.assign(graph_size, false);
		disc.assign(graph_size, 0);
		low.assign(graph_size, 0);
		parent.assign(graph_size, -1);

		rep(i, graph_size)
			if (!visited[i])
				bridgeUtil(i);
	}

	uint32 time;

	uint32 graph_size;
	Graf& graf;

	vector<uint32> bridges;

	bit_vector visited;
	vector<int32> disc;
	vector<int32> low;
	vector<int32> parent;
};

class find_union {
 public:

	find_union() {
	}

	void resize(uint32 size) {
		rank.resize(size);
		parent.resize(size);
		rep(i, size) {
			rank[i] = 0;
			parent[i] = i;
		}
	}

	uint32 find_set(uint32 x) {
		if (x != parent[x]) {
			parent[x] = find_set(parent[x]);
		}
		return parent[x];
	}

	void union_set(uint32 a, uint32 b) {
		uint32 x = find_set(a);
		uint32 y = find_set(b);
		if (x == y) return;

		if (rank[x] > rank[y]) {
			parent[y] = x;
		}
		else {
			parent[x] = y;
		}

		if (rank[x] == rank[y]) {
			rank[y]++;
		}

		return;
	}

 private:
	vector<uint8> rank;
	vector<uint32> parent;
};

const uint64 prime = 0xFFFFFFFB;

class Application {
public:
	Application() {
		numberOfNodes = (uint32)NumberOfNodes();
		myNodeId = (uint32)MyNodeId();
		numberOfIsles = (uint64)NumberOfIsles();
		numberOfBridges = (uint64)NumberOfBridges();
		numberOfActiveNodes = numberOfNodes;

		findunion.resize(numberOfIsles);
		graf.reset(new Graf(numberOfIsles));
	}

	void Run() {
		LoadMyEdgesFromLibrary();
		SolveState();

		while (true) {
			uint32 half = (numberOfActiveNodes + 1) / 2;
			uint32 potential_source = half + myNodeId;

			if (myNodeId >= half) {
				SendState(myNodeId - half);
				return;
			}
			else if (potential_source < numberOfActiveNodes) {
				LoadState(potential_source);
			}
			else {
				goto omit_work;
			}

			SolveState();

			omit_work:

			if (numberOfActiveNodes == 1)
				break;

			numberOfActiveNodes = (numberOfActiveNodes + 1) / 2;
		}

		assert(myNodeId == 0);

		cout << bridges.size() << endl;
	}

	void LoadMyEdgesFromLibrary() {
		uint64_pair edges_range = GetRange(numberOfBridges, myNodeId, numberOfNodes);

		for (uint64 i = edges_range.first ; i < edges_range.second ; i++) {
			uint64 index = (i * prime) % numberOfBridges;
			LoadEdgeFromLibrary(index);
		}
	}

	void LoadEdgeFromLibrary(uint32 index) {
		uint32_pair edge = GetEdge(index);
		edge.first = findunion.find_set(edge.first);
		edge.second = findunion.find_set(edge.second);
		graf->add(edge.first, edge.second, index);
	}

	void SendState(uint32 target) {
		//cerr << myNodeId << " wysyla do " << target << ", krawedzi " << bridges.size() << endl;
		PutUnionStructure(target);
		PutEdges(target);
		Send(target);
	}

	void PutUnionStructure(uint32 target) {
		rep (i, numberOfIsles) {
			PutInt(target, findunion.find_set(i));
		}
	}

	void PutEdges(uint32 target) {
		PutInt(target, bridges.size());
		for (uint32 bridge : bridges)
			PutInt(target, bridge);
	}

	void LoadState(uint32 source) {
		//cerr << myNodeId << " odbiera od " << source << endl;
		Receive(source);
		LoadUnionStructure(source);
		LoadEdges(source);
		//cerr << myNodeId << " odebralo od " << source << endl;
	}

	void LoadUnionStructure(uint32 source) {
		rep (i, numberOfIsles) {
			uint32 root = (uint32)GetInt(source);
			findunion.union_set(i, root);
		}
	}

	void LoadEdges(uint32 source) {
		uint32 count = (uint32)GetInt(source);
		rep (i, count) {
			uint32 id = (uint32)GetInt(source);
			LoadEdgeFromLibrary(id);
		}
	}

	uint32_pair GetEdge(uint64 index) {
		uint32 a = (uint32)BridgeEndA(index);
		uint32 b = (uint32)BridgeEndB(index);
		return uint32_pair(a, b);
	}

	void SolveState() {
		BridgeFinder bridgeFinder(*graf);
		bridgeFinder.bridge();
		vector<uint32>& mosty = bridgeFinder.bridges;
		//debug_print(mosty.size());
		sort_all(mosty);

		for (const edge_type& edge : graf->getAllEdges()) {
			if (!binary_search(all(mosty), edge.second))
				findunion.union_set(edge.first.first, edge.first.second);
		}

		bridges = mosty;
		graf.reset(new Graf(numberOfIsles));
		for (uint32 id : bridges)
			LoadEdgeFromLibrary(id);
	}

	uint32 numberOfActiveNodes;
	uint32 numberOfNodes;
	uint32 myNodeId;
	uint64 numberOfIsles;
	uint64 numberOfBridges;

	find_union findunion;
	unique_ptr<Graf> graf;

	vector<uint32> bridges;
};


int main() {
	ios::sync_with_stdio(0);
	Application application;
	application.Run();
	return 0;
}