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
#include "sabotaz.h"
#include "message.h"

#include <iostream>
#include <stack>
#include <vector>
#include <set>

using namespace std;

struct Edge {
  int dest;
  bool multi;
  Edge(): dest(-1), multi(false) { }
  Edge(int const &dest): dest(dest), multi(false) { }
  Edge(int const &dest, bool const &multi): dest(dest), multi(multi) { }
  ~Edge() { }
  bool operator<(Edge const &rhs) const { return dest != rhs.dest ? dest < rhs.dest : multi < rhs.multi; };
};

struct Vertex {
  set<Edge> nb;
  int d;
  int l;
  int p;
  Vertex(): d(-1), l(-1), p(-1) { }
  ~Vertex() { }
};

typedef vector<Vertex> Graph;


int dfs(Graph &gr, vector< set<Edge>::iterator > &pos, int &dd, int const &i) {
  int result = 0;
  stack<int> st;
  
  st.push(i);
  gr[i].l = gr[i].d = dd++;
  
  while(not st.empty()) {
    int u = st.top();
    
    if(pos[u] != gr[u].nb.end()) {
      int w = (pos[u]++)->dest;
      if(gr[w].d == -1) {
        st.push(w);
        gr[w].p = u;
        gr[w].l = gr[w].d = dd++;
      }
    } else {
      st.pop();
      
      for(set<Edge>::iterator it = gr[u].nb.begin(); it != gr[u].nb.end(); ++it) {
        int v = it->dest;
        if(u == gr[v].p) {
          gr[u].l = min(gr[u].l, gr[v].l);
        } else if(v != gr[u].p) {
          gr[u].l = min(gr[u].l, gr[v].d);
        }
      }
      
      if(gr[u].l == gr[u].d and gr[u].nb.find(Edge(gr[u].p, false)) != gr[u].nb.end()) {
        ++result;
      }
    }
  }
  
  return result;
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  if(MyNodeId() != 0) return 0;
  
  int n = NumberOfIsles();
  int m = NumberOfBridges();
  
  Graph gr(n);
  
  for(int i = 0; i < m; ++i) {
    int a = BridgeEndA(i);
    int b = BridgeEndB(i);
    
    if(a == b) continue;
    
    if(gr[a].nb.find(Edge(b, true)) != gr[a].nb.end()) continue;
    
    if(gr[a].nb.find(Edge(b, false)) != gr[a].nb.end()) {
      gr[a].nb.erase(Edge(b, false));
      gr[b].nb.erase(Edge(a, false));
      gr[a].nb.insert(Edge(b, true));
      gr[b].nb.insert(Edge(a, true));
      continue;
    }
    
    gr[a].nb.insert(Edge(b, false));
    gr[b].nb.insert(Edge(a, false));
  }
  
  int dd = 0;
  int result = 0;
  
  vector< set<Edge>::iterator > pos;
  for(int i = 0; i < n; ++i) pos.push_back(gr[i].nb.begin());
  for(int i = 0; i < n; ++i) {
    if(gr[i].d == -1) result += dfs(gr, pos, dd, i);
  }
  
  cout << result << '\n';
  
  return 0;
}