#include <stdio.h>
#include <stdlib.h>

#define NULL_NODE (-1)
// Used to indicate singleton node.
#define EPHEMERAL_EDGE (-1)
#define NULL_EDGE (-2)

typedef int node;
typedef int edgeIndex;

typedef struct e {              /* The data type used for edges */
  node start;                    /* vertex where the edge starts */
  node end;                      /* vertex where the edge ends */

  edgeIndex prev;               /* previous edge in clockwise direction */
  edgeIndex next;               /* next edge in clockwise direction */
  edgeIndex invers;             /* the edge that is inverse to this one */
} EDGE;

typedef struct graph {

  int numNodes;

  node nextNode;

  edgeIndex *firstEdge;

  int numEdges;

  edgeIndex nextEdge;

  EDGE *edges;

} GRAPH;

typedef struct dq {
  int qLen;

  int startInd;
  int endInd;

  node *q;
} DEQUEUE;

typedef struct dd {

  node rootNode; /* Will be NULL_NODE if white-rooted. */

  GRAPH *graph;

  DEQUEUE *inBuds;

  DEQUEUE *outBuds;
} DANGD;

void mergeBlackSub(DANGD *ddl, DANGD *ddr);
void cloneDANGD(DANGD *src, DANGD *dest);
void matchBud(GRAPH *gr, node ob, node ib);
void initGraph(int numNodes, int numEdges, GRAPH *gr);
void appendGraph(GRAPH *gr1, GRAPH *gr2, node *nOffset, edgeIndex *eOffset);
edgeIndex addEdge(GRAPH *gr, edgeIndex fE, edgeIndex tE);
void deleteNode(GRAPH *gr, node n);
void deleteEdge(GRAPH *gr, edgeIndex e);
void cloneGraph(GRAPH *src, GRAPH *dest);
void test(DANGD *dd, GRAPH *gr);

void enqueueF(DEQUEUE *dq, node n);
void enqueueE(DEQUEUE *dq, node n);
node dequeueF(DEQUEUE *dq);
node dequeueE(DEQUEUE *dq);
int queueSize(DEQUEUE *dq);
void mergeQueues(DEQUEUE *q1, DEQUEUE *q2, DEQUEUE *dest);
void appendQueue(DEQUEUE *q1, DEQUEUE *q2);
void prependQueue(DEQUEUE *q1, DEQUEUE *q2);
void cloneQueue(DEQUEUE *src, DEQUEUE *dest, node offset);