const int N = 1e6;
const int K = 20;

/************************** Treap ********************************/

struct TreapNode {
  static TreapNode* null;
  TreapNode *l, *r, *p;
  int y;
  int size; // размер поддерева
  enum TYPE {VERTEX, EDGE};
  TYPE type; // node-у декартова дерева соответствует или вершина, или ребро исходного графа
  int i; // 0..n-1 -- индекс вершины или ребра
  int level; // уровень на котором живёт вершина, инвариант: f[level].vertexNode[vertex]->level == level
  int hasVertex; // есть ли node-VERTEX в поддереве, из которой торчат рёбра ранга level (adjacent[v][k].size() != 0)
  int hasEdge; // есть ли node-EDGE в поддереве ранга ровно level

  void calc(); // пересчитать size, hasVertex, hasEdge
  void calcToTop(); // пересчитать всё на пути до корня

  TreapNode() {
    memset(this, 0, sizeof(TreapNode));
    p = l = r = null;
  }
  TreapNode( TYPE type, int i, int level ) : type(type), i(i), level(level) {
    y = rand();
    p = l = r = null;
    size = 1;
  }
};
TreapNode* TreapNode::null = new TreapNode();

void split( TreapNode* node, TreapNode* &l, TreapNode* &r, int k ); // получает node, k; возвращает l, r
TreapNode* merge( TreapNode* l, TreapNode* r );
TreapNode* getRoot( TreapNode* node ); // поднимается до корня
int positionInTreap( TreapNode* node ); // поднимается до корня, вычисляем позицию

/************************** Forest ********************************/

struct Forest { // Лес, для каждого дерева которого, храним Эйлеров Обход в treap
  int level; // индекс Forest-а: инвариант f[level].level == level
  TreapNode* vertexNode[N]; // вершине исходного графа соответствует TreapNode
  TreapNode* edgeNode1[N]; // по номеру ребра i (ориентация туда) получить вершину в Treap
  TreapNode* edgeNode2[N]; // по номеру ребра i (ориентация обратно) получить вершину в Treap
  // У i-го ребра концы: edges[i].a, edges[i].b. Ориентация туда: a -> b. Ориентация обратно: b -> a.

  void init(); // Каждое Euler Tour Tree состоит из одной TreapNode, type=VERTEX
  void makeRoot( int vertex ); // используется в cut() и link()
  void cut( int edge ); 
  void link( int edge );
  bool isConnected( int a, int b ); // "внутреннее ребро или внешнее", по-другому "в одной компоненте связности a и b, или в разных"
  // getRoot(f[i].vertexNode[vertex]) -- корень treap, в котором лежит вершина исходного графа vertex в лесе уровня i
  // getRoot(f[i].edgeNode1[edge]) -- корень treap, в котором лежит ребро исходного графа edge в лесе уровня i

  void getSpanningEdges( TreapNode* root, vector<int> &spanning_edges ); // все остовные рёбра ранга k в компоненте root (использует hasEdge)
  int getAllEdges( TreapNode* root, vector<int> &inner_edges );
  // Перебирает все НЕ остовные рёбра ранга k в компоненте root (используя hasVertex), внутренние складывает в inner_edges.
  // Выходит, когда натыкается на внешнее, возвращает номер найденного внешнего, если не нашла, то -1
};

/************************** Собственно Dynamic Connectivity ********************************/

struct Edge { // неориентированное
  int a, b; // вершины-концы
  int rank;
  int multi; // кратность ребра
};

set<int> adjacent[N][K]; // списки смежности рёбер: для каждой вершины, для каждого ранга храним все НЕ ОСТОВНЫЕ рёбра такого ранга

vector<Edge> edges; // все рёбра графа (неориентированные!)
Forest f[K]; // f[i] = остовный лес рёбер ранга 0..i
map<pair<int, int>, int> edgeIndex; // преобразователь пар вершин <a,b> в "индекс ребра"

bool isConnected( int a, int b ); // f[0].isConnected(a, b)
void addEdge( int a, int b ); // edges <- {a, b, 0}, if (!isConnected(a, b)) f[0].link(index of new edge);
void delEdge( int a, int b ); // edgeIndex -> i, if (f[0].edgeNode1[i]) { Код удаления... }
/**
Код удаления...
  k = edges[i].rank
  for (j=k..0) 
    f[j].cut(i)
  for (j=k..0) { // цикл по уровням
    root = выбрали из { f[j].root(edges[i].a), f[j].root(edges[i].b) } минимум по size
    list = f[k].getSpanningEdges(root);
    увеличить ранг всем рёбрам из list
    vector<inner_edges> store;
    outer_edge  = f[k].getAllEdges(root, store);
    if (outer_edge != -1) {
      for (z=0..j) 
        f[z].link(outer_edge)
      break;
    }
  }
*/

/************************** Об этом должны думать все, чтобы не забыть ничего пересчитать ********************************/

// Вспомогательные функции
void updateVertex( int vertex, int level ); // пересчитать всё, что зависит от вершины vertex
void increaseRank( int edge, bool isSpaning ); // пересчитать всё, что зависит от ранга
