#include <string>
#include <vector>
#include <list>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include "TheSocialNetwork.hpp"
#include "disjoint_set.hpp"
using namespace std;

using plank::Disjoint_Set;

int main(int argc, char **argv)
{
  long t0, t1;
  int e1, e2, s1, s2, len;
  bool ok;
  int minn, maxn;
  int maxl, tmp;
  Disjoint_Set d;
  set <int> ls;
  set <string> edges;
  char buf[100];
  int maxm;
  int i;
  class TheSocialNetwork TheClass;
  int retval;
  int n;
  int m;
  vector <int> u;
  vector <int> v;
  vector <int> l;

  if (argc != 2) { fprintf(stderr, "usage: a.out num\n"); exit(1); }

  if ((string) argv[1] == "-") {
    cin >> n >> m;
    while (u.size() < m) { cin >> i; u.push_back(i); }
    while (v.size() < m) { cin >> i; v.push_back(i); }
    while (l.size() < m) { cin >> i; l.push_back(i); }
  } else if (atoi(argv[1]) == 0) {
    n = 6;
    m = 6;
    u.push_back(1);
    u.push_back(2);
    u.push_back(3);
    u.push_back(4);
    u.push_back(5);
    u.push_back(6);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);
    v.push_back(1);
    l.push_back(1);
    l.push_back(7);
    l.push_back(3);
    l.push_back(4);
    l.push_back(6);
    l.push_back(12);
  } else if (atoi(argv[1]) == 1) {
    n = 5;
    m = 7;
    u.push_back(1);
    u.push_back(1);
    u.push_back(1);
    u.push_back(2);
    u.push_back(2);
    u.push_back(3);
    u.push_back(3);
    v.push_back(5);
    v.push_back(3);
    v.push_back(2);
    v.push_back(5);
    v.push_back(3);
    v.push_back(5);
    v.push_back(4);
    l.push_back(1);
    l.push_back(8);
    l.push_back(2);
    l.push_back(3);
    l.push_back(4);
    l.push_back(6);
    l.push_back(9);
  } else if (atoi(argv[1]) == 2) {
    n = 7;
    m = 6;
    u.push_back(1);
    u.push_back(1);
    u.push_back(2);
    u.push_back(2);
    u.push_back(3);
    u.push_back(3);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);
    v.push_back(7);
    l.push_back(7);
    l.push_back(11);
    l.push_back(6);
    l.push_back(9);
    l.push_back(20);
    l.push_back(15);
  } else if (atoi(argv[1]) == 3) {
    n = 8;
    m = 11;
    u.push_back(1);
    u.push_back(1);
    u.push_back(2);
    u.push_back(2);
    u.push_back(3);
    u.push_back(3);
    u.push_back(3);
    u.push_back(4);
    u.push_back(5);
    u.push_back(5);
    u.push_back(7);
    v.push_back(2);
    v.push_back(8);
    v.push_back(3);
    v.push_back(5);
    v.push_back(4);
    v.push_back(6);
    v.push_back(7);
    v.push_back(5);
    v.push_back(6);
    v.push_back(8);
    v.push_back(8);
    l.push_back(2);
    l.push_back(3);
    l.push_back(1);
    l.push_back(6);
    l.push_back(11);
    l.push_back(8);
    l.push_back(9);
    l.push_back(10);
    l.push_back(7);
    l.push_back(4);
    l.push_back(5);
  } else if (atoi(argv[1]) == 4) {
    n = 13;
    m = 56;
    u.push_back(1);
    u.push_back(1);
    u.push_back(1);
    u.push_back(1);
    u.push_back(1);
    u.push_back(1);
    u.push_back(1);
    u.push_back(2);
    u.push_back(2);
    u.push_back(2);
    u.push_back(2);
    u.push_back(2);
    u.push_back(2);
    u.push_back(2);
    u.push_back(3);
    u.push_back(3);
    u.push_back(3);
    u.push_back(3);
    u.push_back(3);
    u.push_back(3);
    u.push_back(3);
    u.push_back(4);
    u.push_back(4);
    u.push_back(4);
    u.push_back(4);
    u.push_back(4);
    u.push_back(4);
    u.push_back(5);
    u.push_back(5);
    u.push_back(5);
    u.push_back(5);
    u.push_back(5);
    u.push_back(6);
    u.push_back(6);
    u.push_back(6);
    u.push_back(6);
    u.push_back(6);
    u.push_back(7);
    u.push_back(7);
    u.push_back(7);
    u.push_back(7);
    u.push_back(7);
    u.push_back(7);
    u.push_back(8);
    u.push_back(8);
    u.push_back(8);
    u.push_back(9);
    u.push_back(9);
    u.push_back(9);
    u.push_back(9);
    u.push_back(10);
    u.push_back(10);
    u.push_back(10);
    u.push_back(11);
    u.push_back(11);
    u.push_back(12);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(7);
    v.push_back(9);
    v.push_back(12);
    v.push_back(13);
    v.push_back(3);
    v.push_back(5);
    v.push_back(8);
    v.push_back(9);
    v.push_back(10);
    v.push_back(12);
    v.push_back(13);
    v.push_back(5);
    v.push_back(6);
    v.push_back(8);
    v.push_back(9);
    v.push_back(10);
    v.push_back(11);
    v.push_back(12);
    v.push_back(5);
    v.push_back(6);
    v.push_back(7);
    v.push_back(9);
    v.push_back(11);
    v.push_back(13);
    v.push_back(7);
    v.push_back(8);
    v.push_back(9);
    v.push_back(11);
    v.push_back(12);
    v.push_back(7);
    v.push_back(8);
    v.push_back(9);
    v.push_back(10);
    v.push_back(13);
    v.push_back(8);
    v.push_back(9);
    v.push_back(10);
    v.push_back(11);
    v.push_back(12);
    v.push_back(13);
    v.push_back(9);
    v.push_back(11);
    v.push_back(12);
    v.push_back(10);
    v.push_back(11);
    v.push_back(12);
    v.push_back(13);
    v.push_back(11);
    v.push_back(12);
    v.push_back(13);
    v.push_back(12);
    v.push_back(13);
    v.push_back(13);
    l.push_back(82);
    l.push_back(240);
    l.push_back(395);
    l.push_back(1041);
    l.push_back(1165);
    l.push_back(1274);
    l.push_back(1540);
    l.push_back(1650);
    l.push_back(1904);
    l.push_back(2306);
    l.push_back(2508);
    l.push_back(3162);
    l.push_back(3380);
    l.push_back(3637);
    l.push_back(3778);
    l.push_back(3913);
    l.push_back(3971);
    l.push_back(4101);
    l.push_back(4148);
    l.push_back(4218);
    l.push_back(4394);
    l.push_back(4434);
    l.push_back(5107);
    l.push_back(6147);
    l.push_back(6280);
    l.push_back(6337);
    l.push_back(6461);
    l.push_back(6490);
    l.push_back(7056);
    l.push_back(8024);
    l.push_back(8373);
    l.push_back(8924);
    l.push_back(8961);
    l.push_back(9058);
    l.push_back(9304);
    l.push_back(9359);
    l.push_back(10899);
    l.push_back(11049);
    l.push_back(11090);
    l.push_back(11174);
    l.push_back(11269);
    l.push_back(11356);
    l.push_back(11547);
    l.push_back(11808);
    l.push_back(12566);
    l.push_back(12591);
    l.push_back(13322);
    l.push_back(13447);
    l.push_back(13667);
    l.push_back(13672);
    l.push_back(15013);
    l.push_back(15319);
    l.push_back(16153);
    l.push_back(16447);
    l.push_back(16454);
    l.push_back(16470);
  } else {
   
    srand48(atoi(argv[1]));
    switch (atoi(argv[1]) % 5) {
      case 0: maxm = 100; break;
      case 1: maxm = 1000; break;
      case 2: maxm = 10000; break;
      case 3: maxm = 100000; break;
      case 4: maxm = 1000000; break;
    }
    m = drand48()*maxm+1;
    maxl = m*2;
    if (m < 100) {
      maxn = m-1;
    } else {
      maxn = m/2;
    }
    if (maxn < 2) maxn = 2;
    for (minn = 2; minn * (minn-1) / 2 < m; minn++) ;
    n = drand48()*(maxn-minn+1)+minn;

    d.Initialize(n);

    while (u.size() < m) {
      e1 = drand48() * n;
      do { e2 = drand48() * n; } while (e1 == e2);
      if (e1 < e2) { tmp = e2; e2 = e1; e1 = tmp; }
      sprintf(buf, "%d %d", e1, e2);
      if (edges.find(buf) != edges.end()) {
        ok = false;
      } else if (d.Get_Set_Ids()->size() == 1) {
        ok = true;
      } else {
        s1 = d.Find(e1);
        s2 = d.Find(e2);
        if (s1 != s2) {
          ok = true;
          d.Union(s1, s2);
        } else {
          ok = false;
        }
      }
      if (ok) {
        edges.insert(buf);
        do { len = drand48()*maxl+1; } while (ls.find(len) != ls.end());
        ls.insert(len);
        u.push_back(e1);
        v.push_back(e2);
        l.push_back(len);
      }
    }
    for (i = 0; i < v.size(); i++) v[i] += 1;
    for (i = 0; i < u.size(); i++) u[i] += 1;
  }

  t0 = time(0);
  retval = TheClass.minimumCut(n, m, u, v, l);
  t1 = time(0);

  if (t1 - t0 > 3) cout << t1 - t0 << " seconds - too slow.\n";
  cout << retval << endl;

  exit(0);
}