Odrediti broj minimalnih pokrivajućih stabala datog povezanog težinskog grafa u kome se ni jedna težina grane ne ponavlja više od 4 puta.

Ulaz:

(Ulazni podaci se nalaze u datoteci stabla.in) U prvom redu ulaza su zapisani brojevi N i M (1 ≤ N,M ≤ 5x10⁴), broj čvorova i broj grana datog grafa. U svakom od narednih M redova zapisana su tri cela broja A, B i W (1 ≤ A,B ≤ N, 1 ≤ W ≤ 2³⁰), koji označavaju da između čvorova A i B postoji grana težine W.

Izlaz:

(Izlazne podatke upisati u datoteku stabla.out) U izlaznu datoteku ispisati ostatak traženog broja minimalnih pokrivajućih stabala datog grafa koji se dobija pri deljenju sa 1000003.

Primer 1:

3 4
1 2 6
1 2 6
2 3 6
3 1 6
3 3 8

5

Objašnjenje.

Sve grane su iste težine, između čvorova 1 i 2 postoje dve grane, a postoji i grana kojoj su oba kraja u čvoru 3.

Primer 2:

6 8
1 2 1
2 3 2
3 4 3
4 5 3
5 6 2
6 1 1
2 6 1
3 5 3

6

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;

const long MaxN = 100001;

const long MOD   = 1000003;


struct Edge{
  long a, b;
  long w;
  
  Edge(){}  
  Edge(long _a, long _b, long _w):a(_a), b(_b), w(_w){}
  
  friend bool operator<(const Edge &a, const Edge &b){
    return a.w < b.w;
  }
};


Edge e[MaxN];
long n, m;

long rez;

bool root[MaxN];
long otac[MaxN];


void init_disjoint(){
  for (long i = 0; i < MaxN; i++){
    root[i] = true;
    otac[i] = 1;
  }
}

long group(long x){
  long tmp = x, tmp1;
  while (!root[x]) x = otac[x];
  while (!root[tmp]){
    tmp1 = otac[tmp];
    otac[tmp] = x;
    tmp = tmp1;
  }
  return x;
}

void merge(long _x, long _y){
  long x = group(_x), y = group(_y);
  if (x == y) return;
  
  if (otac[x] > otac[y]){
    otac[x] += otac[y];
    otac[y] = x;
    root[y] = false;
  }
  else{
    otac[y] += otac[x];
    otac[x] = y;
    root[x] = false;
  }
}

void count2(long *a, long *b, long idBr){
  if (idBr == 2) rez *= 2;
}

void count3(long *a, long *b, long idBr){
  if (idBr == 2) rez *= 3;
  else if (idBr == 3){
    if ((a[0] == a[1] && b[0] == b[1]) || (a[0] == a[2] && b[0] == b[2]) || (a[1] == a[2] && b[1] == b[2])) rez *= 2;
    else rez *= 3;
  }
  else if (idBr == 4){
    if ((a[0] == a[1] && b[0] == b[1]) || (a[0] == a[2] && b[0] == b[2]) || (a[1] == a[2] && b[1] == b[2])) rez *= 2;
  }
}

void count4(long *a, long *b, long idBr){
  bool dva = false;
  for (int i = 0; !dva && i < 4; i++) for (int j = i + 1; !dva && j < 4; j++)
    if (a[i] == a[j] && b[i] == b[j])  dva = true;
  
  bool usamljenaGrana = false;
  for (int i = 0; !usamljenaGrana && i < 4; i++){
    usamljenaGrana = true;
    for (int j = 0; usamljenaGrana && j < 4; j++){
      if (i == j) continue;
      if (a[i] == a[j] || a[i] == b[j] || b[i] == a[j] || b[i] == b[j]) usamljenaGrana = false;
    }
  }
  
  int stepen[8];
  for (int i = 0; i < 8; i++) stepen[i] = 0;
  for (int i = 0; i < 4; i++){
    stepen[a[i]-1]++;
    stepen[b[i]-1]++;
  }
  sort(&stepen[0], &stepen[idBr]);
  
  if (idBr == 2) rez *= 4;
  else if (idBr == 3){
    if (stepen[0] == 2 && stepen[1] == 2 && stepen[2] == 4) rez *= 4;
    else if (stepen[0] == 1 && stepen[1] == 3 && stepen[2] == 4) rez *= 3;
    else rez *= 5;
  }
  else if (idBr == 4){
    if (stepen[0] == 2 && stepen[1] == 2 && stepen[2] == 2 && stepen[3] == 2) rez *= 4;
    else if (dva && usamljenaGrana) rez *= 3;
    else{
      if (dva) rez *= 2;
      else if (stepen[0] == 1 && stepen[1] == 2 && stepen[2] == 2 && stepen[3] == 3) rez *= 3;
    }
  }
  else if (idBr == 5){
    if (dva) rez *= 2;
    else if (usamljenaGrana) rez *= 3;
  }
  else if (idBr == 6){
    if (dva) rez *= 2;
  }
}
      

void count(long *paket, long br){
  if (br <= 1) return;
  else{
    map<long, long> mapa;
    long idBr = 1;
    long a[4], b[4];
    
    for (int i = 0; i < br; i++){
      long g1 = group(e[paket[i]].a);
      long g2 = group(e[paket[i]].b);
      if (mapa[g1] == 0) mapa[g1] = idBr++;
      if (mapa[g2] == 0) mapa[g2] = idBr++;
      a[i] = mapa[g1]; b[i] = mapa[g2];
      if (a[i] > b[i]) swap(a[i], b[i]);
    }
    
    idBr--;

    if (br == 4) count4(a, b, idBr);
    else if (br == 3) count3(a, b, idBr);
    else if (br == 2) count2(a, b, idBr);
    
    rez %= MOD;
  }
}
      
void Kruskal(){
  init_disjoint();
  sort(&e[0], &e[m]);
  
  rez = 1; // pretpostavljam da je graf povezan
  
  long last = e[0].w;
  
  long nextGroup[4];
  long br = 0;
  
  nextGroup[br++] = 0;
  
  for (long i = 1; i < m; i++){
    if (e[i].w != last){
      count(nextGroup, br);
      
      for (int j = 0; j < br; j++) merge(e[nextGroup[j]].a, e[nextGroup[j]].b);
  
      br = 0;
      last = e[i].w;
      
    }
    
    long g1 = group(e[i].a);
    long g2 = group(e[i].b);
    
    if (g1 != g2) nextGroup[br++] = i;
  }
  
  count(nextGroup, br);
  for (int j = 0; j < br; j++) merge(e[nextGroup[j]].a, e[nextGroup[j]].b);
}
      
void init(){
  FILE *f;
  f = fopen("stabla.in", "r");
  fscanf(f,"%ld %ld", &n, &m);
  long a, b, w;
  long k = 0;
  for (long i = 0; i < m; i++){
    fscanf(f,"%ld %ld %ld", &a, &b, &w);
    if (a != b)  e[k++] = Edge(a, b, w);
  }
  m = k;
  fclose(f);
}


int main(){
  init();
  Kruskal();
  
  long gr = group(1);
  for (long i = 1; i < n; i++){
    if (group(i) != gr){
      rez = 0;
      break;
    }
  }
  
  FILE *f;
  f = fopen("stabla.out", "w");
  fprintf(f, "%ld\n", rez);
  fclose(f);
  
  return 0;
}