#include <cassert>
#include <cmath>
#include <cstdio>
#include <iostream>

#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int count_sets(const vector<int> &v);

double drand() {
  return double(rand())/double(RAND_MAX);
}

// Poner a 1 para imprimir los vectores por pantalla
int VRBS=1;                     // verbosity level

int main() {
  int N,M,xmax,ntimes;
#if 1 || defined(DOMJUDGE)
  N=1000000;            // Numero de conjuntos
  M=5;                   // Tamano maximo de los conjuntos
  xmax=-1; // Maximo elemento del conjunto (-1 indica infinito)
  ntimes=40; // Number of times the problem is repeated
  VRBS=0;
#else
  // Caso de prueba
  N=20;   // Numero de conjuntos
  M=6;    // Tamano maximo de los conjuntos
  xmax=10; // Maximo elemento del conjunto (-1 indica infinito)
  ntimes=1;       // Number of times the problem is repeated
  VRBS=1;
#endif
  double frac = 0.1;   // Controla la cantidad de sets repetidos
  // Generamos N conjuntos aleatorios
  int vsets_sz = N;
  vector< set<int> > vsets(vsets_sz);
  srand(19400310);              // seed = CN birth date, LOL!!
  
  for (int j=0; j<vsets_sz; j++) {
    int sz = rand()%M+1;
    set<int> &s = vsets[j];
    for (int k=0; k<sz; k++) {
      int x = rand();
      if (xmax>0) x %= xmax;
      s.insert(x);
    }
  }

  // Lo repetimos ntimes veces, solo para medir
  // mejor los tiempos
  for (int m=0; m<ntimes; m++) {

    // Volver a setear la semilla del RNG, porque el usuario
    // puede haber usado random tambien, entonces el resultado
    // no seria deterministico 
    srand(19400310+m);
    vector<int> indices(N),indices1;
    for (int j=0; j<N; j++) {
      int k=j;
      // Con una cierta probabilidad introducimos una colision
      if (drand()<frac) k = rand()%vsets_sz;
      indices[j] = k;
    }
    indices1 = indices;
    random_shuffle(indices.begin(),indices.end());
    indices = indices1;

    // Generamos el vector apendizando N de estos
    // conjuntos (puede haber colisiones)
    vector<int> v;                                
    int next = 0;
    for (int j=0; j<N; j++) {
      int k= indices[j];
      set<int> &s = vsets[k];
      set<int>::iterator q = s.begin();
      while (q!=s.end()) v.push_back(*q++);
      random_shuffle(v.begin()+next,v.end());
      v.push_back(-1);
      next = v.size();
    }

    if (VRBS) {
      unsigned int j=0, js=0;
      while(j<v.size()) {
        printf("S%d={",js);
        while (v[j]>=0) printf("%d ",v[j++]);
        printf("}\n"); j++; js++;
      }
      printf("fin de los conjuntos -----------\n");
    }
  
    if (VRBS) 
      printf("Numero de conjuntos distintos ");
    printf("%d\n",count_sets(v));
  }
  return 0;
}

//================================================================
//  PARTICIPANTES DEL TORNEO SOLO DEBERIAN MODIFICAR
//  DE AQUI PARA ABAJO
//================================================================

int count_sets(const vector<int> &v) {
  set< set<int> > ssets;
  unsigned int j=0; 
  while(j<v.size()) {
    set<int> s;
    while (v[j]>=0) s.insert(v[j++]);
    j++;
    ssets.insert(s);
  }
  return ssets.size();
}