1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>		//UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>		//do setprecision
#include <ctime>
#include <complex>
#include <unordered_map>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;

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

const int inf = 1e9;

#define MR 200010
int n, m, t, pre[MR], p[MR], low[MR];
 
 
map < pair <int,int>, bool> Wielokrotne;
map < pair <int,int>, bool> :: iterator it;
vector <pair<int,bool>> G[MR];
/*
  n - liczba wierzcholkow
  pre[1..n] - tablica numeracji pre-order
  p[1..n] - tablica poprzednikow (tzn. do wierzch. i-tego przeszlismy z wierzch. P[i])
  low[1..n] - tablica szukanej funkcji Low
*/
 

void visit(int nr, int par)
{
	p[nr] = par;
	pre[nr]= ++t;							//przydzielenie numerka w numeracji pre-order    
	low[nr] = pre[nr];							//low[nr] nie moze byc wieksze niz pre[nr]
	for(int i = 0; i < (int)G[nr].size(); i++)	//petla po sasiadach wierzch. nr	
		if(G[nr][i].ST != par)					//nie rozwazamy ojca
			if(!pre[G[nr][i].ST])				//odpal sie dla synow i porownuj ich low
			{
				visit(G[nr][i].ST, nr);	
				if(low[nr] > low[G[nr][i].ST])
					low[nr] = low[G[nr][i].ST];
			}
			else								//dla odwiedzonych spr numer pre-order
				if(low[nr] > pre[G[nr][i].ST])
					low[nr] = pre[G[nr][i].ST];
	//wyznacz mosty, kazdy wierzcholek niekorzen, ktory ma low[v] = pre[v] tworzy most z ojcem		
	for(int i = 0; i < (int)G[nr].size(); i++)	//spr mosty
		if(p[G[nr][i].ST] == nr && low[G[nr][i].ST] == pre[G[nr][i].ST])	//spr czy to na pewno syn
			G[nr][i].ND = 1;
		else if(G[nr][i].ST == par && low[nr] == pre[nr])	//spr czy tworzy most z ojcem
			G[nr][i].ND = 1;
}//visit

//int BridgeEndB(int i)
//{
//	if(i < 3) return (i+1)%3;
//	return 2;
//}
int main()
{
	int nr = MyNodeId();
	if(!nr)
	{
		n = NumberOfIsles();
		m = NumberOfBridges();
		REP(i,m)
		{
			int a = BridgeEndA(i);
			int b = BridgeEndB(i);
			if(a > b) swap(a,b);
			else if(a == b) continue;
			it = Wielokrotne.find(MP(a,b));
			if(it != Wielokrotne.end())
			{
				it->ND = 1;
				continue;
			}
			else Wielokrotne[MP(a,b)] = 0;
			G[a].PB(MP(b,0));
			G[b].PB(MP(a,0));
		}
		REP(i,n)
			if(!pre[i])
			{
				t = 0;
				visit(i, -1);
			}
		
		int res = 0;
		REP(i,n)REP(j,G[i].size())
			if(!Wielokrotne[MP(min(i,G[i][j].ST), max(i,G[i][j].ST))]) res += G[i][j].ND;

		printf("%d\n", res/2);
	}
	return 0;
}