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

typedef struct set set;
typedef struct element element;
typedef struct bucket bucket;
typedef struct parent parent;

struct element {
    int id;
    element* next;
    element* prev;
    set* set;
};

struct bucket {
    int size;
    bucket* prev;
    bucket* next;
    set* head;
};

struct set {
    int id;
    set* next;
    set* prev;
    element* head;
    bucket* bucket;
};

struct parent {
    element* pos;
    parent* next;
};

element* new_element(int id, set* s) {
    element* el = malloc(sizeof(element));
    el->id = id;
    el->set = s;
    el->prev = el->next = NULL;
    return el;
}

element* insert_element(set* s, int id) {
    element* el = new_element(id, s);
    if (s->head) {
        el->next = s->head;
        s->head->prev = el;
    }
    s->head = el;
    return el;
}

set* new_set(int id) {
    set* s = malloc(sizeof(set));
    s->id = id;
    s->prev = s->next = NULL;
    s->head = NULL;
    s->bucket = NULL;
    return s;
}

parent* new_parent(element* el) {
    parent* p = malloc(sizeof(parent));
    p->pos = el;
    p->next = NULL;
    return p;
}

void insert_parent(parent** parents, element* el) {
    int id = el->id;
    parent* p  = new_parent(el);
    if (parents[id]) {
        p->next = parents[id];
    }
    parents[id] = p;
}

bucket* new_bucket(set* s, int size) {
    bucket* b = malloc(sizeof(bucket));
    b->size = size;
    b->prev = b->next = NULL;
    b->head = s;
    return b;
}

void insert_set(set* s, bucket* b) {
    s->next = b->head;
    b->head->prev = s;
    b->head = s;
}

void remove_element(element* el) {
    if (el->next) {
        el->next->prev = el->prev;
    }
    if (el->prev) {
        el->prev->next = el->next;
    } else {
        el->set->head = el->next;
    }
    demote(el->set);
    free(el);
}

void remove_parents(int id, parent** parents) {
    parent* temp;
    parent* p = parents[id];
    while (p != NULL) {
        remove_element(p->pos);
        temp = p;
        p = p->next;
        free(temp);
    }
}

void remove_bucket(bucket* b) {
    if (b->prev) {
        b->prev->next = b->next;
    }
    if (b->next) {
        b->next->prev = b->prev;
    }
    free(b);
}

void demote(set* s) {
    detach_set(s);
    int size = s->bucket->size;
    bucket* attach_point;
    if (s->bucket->prev) {
        attach_point = s->bucket->prev;    
    } else if (s->bucket->head) {
        attach_point = s->bucket;
    } else {

    }
        remove_bucket(s->bucket);
    attach_set(s, size, b);
}

void detach_set(set* s) {
    if (s->next) {
        s->next->prev = s->prev;
    }
    if (s->prev) {
        s->prev->next = s->next;
    } else {
        s->bucket->head = s->next;
    }
}

void attach_set(set* s, int size, bucket* b) {
    if (b->size == size) {
        insert_set(s, b);
    } else {
        bucket* nb =  new_bucket(s, size);
        nb->prev = b;
        nb->next = b->next;
    }
}

void greedy(bucket* head, parent** parents) {
    bucket* b = head;
    for(set* s=b->head; s != NULL; s = s->next) {
        for (element* el = s->head; el != NULL; el = el->next) {
            remove_parents(el->id, parents);
        }
    }
}

int main(int argc, char* argv[]) {
    FILE* file = fopen(argv[1], "r");
    int n_sets, n_elements = 0;
    int current_element = 0;
    bucket *tail, *head = NULL;
    fscanf(file, "%d %d", &n_sets, &n_elements);
    parent** parents = malloc(n_elements*sizeof(parent*));
    for (int element_id = 0; element_id < n_elements; element_id++) {
        parents[element_id] = NULL;
    }

    for(int current_set = 0; current_set < n_sets; current_set++) {
        fscanf(file, "%d", &n_elements);
        set* s = new_set(current_set);
        bucket* current_bucket = tail;
        int j;
        for(j = 0; j < n_elements; j++) {
            fscanf(file, "%d", &current_element);
            element* el = insert_element(s, current_element);
            insert_parent(parents, el);
            if (current_bucket && current_bucket->size < j) {
               current_bucket = current_bucket->next;
            }
        }
        if (!current_bucket) {
            bucket* b = new_bucket(s, j);
            b->prev = head;
            if (head) {
                head->next = b;
            } else {
                head = tail = b;
            }
        } else if (current_bucket->size == j) {
            insert_set(s, current_bucket);
        } else if (current_bucket->size > j) {
            bucket* b =  new_bucket(s, j);
            b->next = current_bucket;
            if (current_bucket->prev) {
                b->prev = current_bucket->prev;
            } else {
                tail = b;     
            }
            current_bucket->prev = b;
        }
    }
    return 0;
}