#pragma warning(disable:4996)
#pragma warning(disable:4244)
#pragma warning(disable:4239)
#pragma warning(disable:4018)

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <memory>
#include <vector>
#include <functional>
#include <array>
#include <tuple>
#include <cassert>
#include <time.h>
#include <set>
#include <string>
#include <ctime>

using namespace std;

typedef unsigned long long ull;
typedef string Filename;

//const int BLOCK = 8000;
//const int BLOCK = 15000;
const int BLOCK = 3100;
//const int BLOCK = 8;
const int ALL_BYTES = 170000;
unsigned char gl_buf[ALL_BYTES + 3000];

vector<unsigned int> ex;
set<unsigned int> ss;
struct RNG {
    int operator() (int n) {
        return std::rand() / (1.0 + RAND_MAX) * n;
    }
};

//double tot_sort_time, tot_join_time;//

void prepare_file_without_memory() {
    FILE* input = fopen("input.bin", "wb");
    //setvbuf(input, NULL, _IONBF, BUFSIZ);
    const int n = 1000;
    //const int n = 5;
    //const int n = 650000;
    //const int n = 200000;//////..

    fwrite(&n, 4, 1, input);

    for (int i = 0; i < n; i++) {
        unsigned int cur = i + 1;
        unsigned int cur2 = (i + 1) % n + 1;
        fwrite(&cur, 4, 1, input);
        fwrite(&cur2, 4, 1, input);
    }
    fclose(input);
}

void prepare_file() {
    FILE* input = fopen("input.bin", "wb");

    const int n = 10;
    //const int n = 600000;
    //const int n = 30000;
    for (int i = 1; i <= n; i++) {
        //unsigned int cur = rand() % (1 << 30);
        unsigned int cur = i;
        if (ss.find(cur) != ss.end()) {
            i--;
            continue;
        }
        ss.insert(cur);
        ex.push_back(cur);
    }
    random_shuffle(ex.begin(), ex.end(), RNG());
    fwrite(&n, 4, 1, input);

    vector<pair<int, int> > edges;
    for (int i = 0; i < n; i++) {
        //edges.push_back({ ex[i], ex[(i + 1) % n] });
        edges.push_back(make_pair( ex[i], ex[(i + 1) % n] ) );
    }

    random_shuffle(edges.begin(), edges.end());

    for (int i = 0; i < n; i++) {
        fwrite(&edges[i].first, 4, 1, input);
        fwrite(&edges[i].second, 4, 1, input);
    }

    fclose(input);

    int min_element_pos, min_element = (1 << 30) + 1;

    for (int i = 0; i < ex.size(); i++) {
        if (ex[i] < min_element) {
            min_element = ex[i];
            min_element_pos = i;
        }
    }
    rotate(ex.begin(), ex.begin() + min_element_pos, ex.end());
}

void prepate_file_test() {
   FILE* input = fopen("input.bin", "wb");
   vector<unsigned int> v{4, 1, 2, 2, 3, 2, 4};
   fclose(input);
}

void check_file(const char* filename, int ln = 1) {
    cerr << "---" << endl;
    cerr << filename << endl;
    FILE* input = fopen(filename, "rb");
    unsigned int cur;
    //unsigned long long cur;
    int cnt = 0;
    while (fread(&cur, 4, 1, input)) {
        cerr << (int)cur << " ";
        cnt = (cnt + 1) % ln;
        if (cnt == 0) {
            cerr << endl;
        }
    }
    fclose(input);
}

void check_file_sort(const char* filename, int ln = 1) {
    cerr << "---" << endl;
    cerr << filename << endl;
    FILE* input = fopen(filename, "rb");
    unsigned long long n;
    fread(&n, 8, 1, input);
    cerr << n << endl;
    unsigned long long cur;

    int cnt = 0;
    while (fread(&cur, 8, 1, input)) {
        cerr << (unsigned long long)cur << " ";
        cnt = (cnt + 1) % ln;
        if (cnt == 0) {
            cerr << endl;
        }
    }
    fclose(input);
}

void check_output() {
    FILE* input = fopen("output.bin", "rb");
    unsigned int cur;
    vector<unsigned int> res;
    while (fread(&cur, 4, 1, input)) {
        res.push_back(cur);
    }

    if (ex != res) {
        cout << "wrong" << endl;
        for (int i = 0; i < ex.size(); i++) {
            if (ex[i] != res[i]) {
                cout << i << " " << ex[i] << " " << res[i] << endl;
            }
        }
    }
    else {
        cout << "ok" << endl;
    }
}


struct Link {
    unsigned int key;
    unsigned int next;
    Link() {}
    Link(unsigned int k, unsigned int nx) : key(k), next(nx) {}
    bool operator < (const Link &A) const {
        return key < A.key;
    }
    //~Link() = default;
};

Filename get_filename(int id, const char* source) {
    return string(source) + to_string(static_cast<long long>(id) );
}


template<typename T>
Filename do_simple_sort(int l, int r, int id, const char* filename, unsigned int offset) {
    T* sbuf = (T*)gl_buf;
    FILE* inp = fopen(filename, "rb");
    unsigned int uno_sz = sizeof(T);
    fseek(inp, l * uno_sz + offset, SEEK_SET);
    int sz = r - l + 1;

    fread(sbuf, uno_sz, sz, inp);
    fclose(inp);

    sort(sbuf, sbuf + sz);

    Filename output_file_name_id = get_filename(id, filename);

    FILE* out = fopen(output_file_name_id.c_str(), "wb");
    //setvbuf(out, NULL, _IONBF, BUFSIZ);
    fwrite(sbuf, uno_sz, sz, out);
    fclose(out);

    return output_file_name_id;
}



template<typename T>
struct FileReader {
    T* buf;
    int len, cur_block, sz, block_size;
    unsigned int uno_sz;
    FILE* inp;

    void reset(const char* filename, int w, int file_len, int block_sz) {
        buf = (T*)(gl_buf + w);
        block_size = block_sz;
        uno_sz = sizeof(T);
        len = file_len;
        cur_block = -1;
        inp = fopen(filename, "rb");
        load(0);
    }

    void load(int idx) {
        int block = idx / block_size;
        if (cur_block != block) {
            cur_block = block;
            fseek(inp, uno_sz * block_size * block, SEEK_SET);
            sz = min(block_size, len - block * block_size);
            fread(buf, uno_sz, sz, inp);
        }
    }

    T get(int idx) {
        load(idx);
        return buf[idx % block_size];
    }
};


template<typename T>
Filename merge(int l, int r, const vector<Filename>& inputs, const int PARTS,
    const vector<int>& file_lens, int to_id, const char* filename) {
    //cerr << "merge " << l << " " << r <<  " " << to_id << " " << filename << endl;
    //check_file(inputs[0].c_str(), 2);
    //check_file(inputs[1].c_str(), 2);
    FileReader<T> file_readers[4];

    Filename output_file_name_id = get_filename(to_id, filename);
    FILE* out = fopen(output_file_name_id.c_str(), "wb");
    //setvbuf(out, NULL, _IONBF, BUFSIZ);

    const int block_sz = ALL_BYTES / sizeof(T) / (PARTS + 1);
    //cerr << "block_sz " << block_sz << " " << l << " " << r << endl;
    vector<int> cur_ptrs(PARTS);

    for (int i = 0; i < PARTS; i++) {
        //cerr << file_lens[i] << " " << inputs[i] << endl;
        file_readers[i].reset(inputs[i].c_str(), sizeof(T) * i * block_sz, file_lens[i], block_sz);
        //setvbuf(file_readers[i].inp, NULL, _IONBF, BUFSIZ);
    }

    T* output_buf = (T*)(gl_buf + PARTS * sizeof(T) * block_sz);
    int out_cnt = 0;

    while (true) {
        int pos_min = -1;
        T min_element, cons;
        for (int i = 0; i < PARTS; i++) {
            if (cur_ptrs[i] < file_lens[i]) {
                cons = file_readers[i].get(cur_ptrs[i]);
                if (pos_min == -1 || cons < min_element) {
                    min_element = cons;
                    pos_min = i;
                }
            }
        }
        //cerr << "pos_min: " << pos_min << endl;
        if (pos_min == -1) {
            break;
        }

        cur_ptrs[pos_min]++;
        //fwrite(&min_element, sizeof(T), 1, out);

        output_buf[out_cnt++] = min_element;
        if (out_cnt == block_sz) {
            fwrite(output_buf, sizeof(T), out_cnt, out);
            out_cnt = 0;
        }
    }

    if (out_cnt > 0) {
        fwrite(output_buf, sizeof(T), out_cnt, out);
        out_cnt = 0;
    }

    fclose(out);

    for (int i = 0; i < PARTS; i++) {
        fclose(file_readers[i].inp);
    }
    //cerr << "finished" << endl;
    return output_file_name_id;
}

template<typename T>
Filename ext_sort(int l, int r, int id, const char* filename, unsigned int offset) {
    //cerr << "sort " << l << " " << r << " " << id << " " << filename << " " << offset << endl;
    if (id == 0) {
        //BLOCK = ALL_BYTES / 2 / sizeof(T);

    }

    //clock_t begin = clock();

    if (r - l + 1 <= ALL_BYTES / sizeof(T)) {
        Filename res = do_simple_sort<T>(l, r, id, filename, offset);

        //clock_t end = clock();
        //double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
        if (id == 0) {
            //tot_sort_time += elapsed_secs;
        }

        return res;
    }
    const int PARTS = 4;
    int all_sz = r - l + 1;
    int base_chunk_len = all_sz / PARTS;

    vector<int> lens(PARTS);
    for (int i = 0; i < PARTS; i++) {
        lens[i] = base_chunk_len;
    }
    for (int i = 0; i < all_sz % PARTS; i++) {
        lens[i]++;
    }
    //cerr << "all sz chunk sz: " << all_sz << " " <<  chunk_sz << endl;
    vector<Filename> results(PARTS);
    int lb = l;
    for (int i = 0; i < PARTS; i++) {
        int rb = lb + lens[i] - 1;
        //cerr << "will call: " << lb << " " << rb << endl;
        results[i] = ext_sort<T>(lb, rb, id * PARTS + i + 1, filename, offset);
        lb += lens[i];
    }

    Filename res = merge<T>(l, r, results, PARTS, lens, id, filename);
    for (int i = 0; i < PARTS; i++) {
        remove(results[i].c_str());
    }
    if (id == 0) {
        //BLOCK = 1500;
    }

    //clock_t end = clock();
    //double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    if (id == 0) {
        //tot_sort_time += elapsed_secs;
    }

    return res;
}

void prepare_link_files(const char* direct_filename, const char* reverse_filename, FILE* input_file, unsigned int n) {
    Link* sbuf = (Link*)gl_buf;
    FILE* reverse_file = fopen(reverse_filename, "wb");
    FILE* direct_file = fopen(direct_filename, "wb");
    //const int block_sz = ALL_BYTES / sizeof(Link);
    const int block_sz = BLOCK;
    for (int i = 0; i < n; i += block_sz) {
        int sz = min(block_sz, (int)n - i);
        fread(sbuf, sizeof(Link), sz, input_file);

        fwrite(sbuf, sizeof(Link), sz, direct_file);

        for (int j = 0; j < sz; j++) {
            Link& cur = sbuf[j];
            swap(cur.key, cur.next);
        }

        fwrite(sbuf, sizeof(Link), sz, reverse_file);

    }

    fclose(reverse_file);
    fclose(direct_file);
}

template<typename T1, typename T2, typename Tres>
void join(const char* first_filename, const char* second_filename,
    const char* result_filename, function<Tres(const T1&, const T2&)> joiner) {
    const int WORK_SZ = ALL_BYTES / (sizeof(T1) + sizeof(T2) + sizeof(Tres));
    //clock_t begin = clock();

    T1* sbuf = (T1*)gl_buf;
    T2* qbuf = (T2*)(gl_buf + WORK_SZ * sizeof(T1));
    Tres* output_buf = (Tres*)(gl_buf + WORK_SZ * (sizeof(T1) + sizeof(T2)));

    unsigned int ptr1 = WORK_SZ, ptr2 = WORK_SZ;
    unsigned int sz1 = 0, sz2 = 0, sz_output = 0;
    FILE* result_file = fopen(result_filename, "wb");

    FILE* t1_file = fopen(first_filename, "rb");
    FILE* t2_file = fopen(second_filename, "rb");

    while (true) {
        if (ptr1 >= sz1) {
            sz1 = fread(sbuf, sizeof(T1), WORK_SZ, t1_file);
            if (sz1 <= 0) {
                break;
            }
            ptr1 = 0;
        }

        if (ptr2 >= sz2) {
            sz2 = fread(qbuf, sizeof(T2), WORK_SZ, t2_file);
            if (sz2 <= 0) {
                break;
            }
            ptr2 = 0;
        }

        while (ptr1 < sz1 && ptr2 < sz2 && sbuf[ptr1].key < qbuf[ptr2].key) {
            ptr1++;
        }

        while (ptr2 < sz2 && ptr1 < sz1 && qbuf[ptr2].key < sbuf[ptr1].key) {
            ptr2++;
        }

        if (ptr1 < sz1 && ptr2 < sz2 && sbuf[ptr1].key == qbuf[ptr2].key) {
            output_buf[sz_output] = joiner(sbuf[ptr1], qbuf[ptr2]);
            sz_output++; ptr1++; ptr2++;
            if (sz_output == WORK_SZ) {
                fwrite(&output_buf[0], sizeof(Tres), WORK_SZ, result_file);
                sz_output = 0;
            }

        }

    }

    if (sz_output > 0) {
        fwrite(&output_buf[0], sizeof(Tres), sz_output, result_file);
        sz_output = 0;
    }

    fclose(result_file);
    fclose(t1_file);
    fclose(t2_file);

    //clock_t end = clock();
    //double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    //tot_join_time += elapsed_secs;
}


Link joiner(Link A, Link B) {
    Link res(B.next, A.next);
    return res;
}

Filename prepare_next_next_file(const char* direct_filename, const char* reverse_filename, int n) {
    Filename next_next_filename = get_filename(n, "next_next");
    join<Link, Link, Link>(direct_filename, reverse_filename, next_next_filename.c_str(), joiner);

    return next_next_filename;

}


tuple<Filename, Filename, Filename> next_next(const char* input_name, unsigned int n) {
    FILE* input_file = fopen(input_name, "rb");

    Filename direct_filename = get_filename(n, "direct");
    Filename reverse_filename = get_filename(n, "reverse");

    prepare_link_files(direct_filename.c_str(), reverse_filename.c_str(), input_file, n);

    fclose(input_file);

    Filename result_direct_file = ext_sort<Link>(0, n - 1, 0, direct_filename.c_str(), 0);
    Filename result_reverse_file = ext_sort<Link>(0, n - 1, 0, reverse_filename.c_str(), 0);
    Filename next_next_filename = prepare_next_next_file(result_direct_file.c_str(), result_reverse_file.c_str(), n);
    Filename sorted_next_next_filename = ext_sort<Link>(0, n - 1, 0, next_next_filename.c_str(), 0);

    remove(next_next_filename.c_str());
    remove(direct_filename.c_str());
    remove(reverse_filename.c_str());

    return make_tuple(move(result_direct_file), move(result_reverse_file), move(sorted_next_next_filename));
}

void transform_file_from_irunner(FILE* input, const char* input_normal_name, unsigned int n) {
    ull* sbuf = (ull*)gl_buf;
    FILE* normal_file = fopen(input_normal_name, "wb");

    for (int i = 0; i < n; i += BLOCK) {
        int sz = min(BLOCK, (int)n - i);
        fread(sbuf, 8, sz, input);
        fwrite(sbuf, 8, sz, normal_file);
    }
    fclose(normal_file);
}


void transform_output_to_irunner(const char* output_name, const char* direct_name, const char* next_next_name, unsigned int n) {
    FILE* output = fopen(output_name, "wb");
    FILE* direct_file = fopen(direct_name, "rb");
    FILE* next_next_file = fopen(next_next_name, "rb");

    Link* sbuf = (Link*)gl_buf;
    Link* qbuf = (Link*)(gl_buf + BLOCK * sizeof(Link));

    for (int i = 0; i < n; i += BLOCK) {
        int sz = min(BLOCK, (int)n - i);
        fread(sbuf, sizeof(Link), sz, direct_file);
        fread(qbuf, sizeof(Link), sz, next_next_file);

        for (int j = 0; j < sz; j++) {
            unsigned int from_d = sbuf[j].key;
            unsigned int to_d = sbuf[j].next;
            unsigned int to_n = qbuf[j].next;

            fwrite(&from_d, 4, 1, output);
            fwrite(&to_d, 4, 1, output);
            fwrite(&to_n, 4, 1, output);
        }
    }

    fclose(output);
    fclose(direct_file);
    fclose(next_next_file);
}

struct NodeWeight {
    unsigned int key;
    unsigned int weight;
    NodeWeight() {};
    NodeWeight(int k, int w) : key(k), weight(w) {};
    bool operator < (const NodeWeight& other) const {
        return key < other.key;
    }
};


Filename prepare_weights(const char* from, int n) {
    FILE* input = fopen(from, "rb");

    Link* sbuf = (Link*)gl_buf;

    Filename output_name = get_filename(n, "weights");
    FILE* output = fopen(output_name.c_str(), "wb");

    for (int i = 0; i < n; i += BLOCK) {
        unsigned int sz = min(BLOCK, n - i);
        fread(sbuf, sizeof(Link), sz, input);
        for (int j = 0; j < sz; j++) {
            NodeWeight cur(sbuf[j].key, 1);
            fwrite(&cur, sizeof(NodeWeight), 1, output);
        }
    }

    fclose(output);
    fclose(input);

    Filename sorted_weights_name = ext_sort<Link>(0, n - 1, 0, output_name.c_str(), 0);

    return sorted_weights_name;
}

//double tot_flip_coins = 0.0;

Filename flip_coins(const char* input_now, int n) {
    //clock_t begin = clock();

    FILE* input = fopen(input_now, "rb");

    Link* sbuf = (Link*)gl_buf;

    Filename output_name = get_filename(n, "coins");
    FILE* output = fopen(output_name.c_str(), "wb");

    for (int i = 0; i < n; i += BLOCK) {
        unsigned int sz = min(BLOCK, n - i);
        fread(sbuf, sizeof(Link), sz, input);
        for (int j = 0; j < sz; j++) {
            NodeWeight cur(sbuf[j].key, (unsigned int)rand() % 2);
            fwrite(&cur, sizeof(NodeWeight), 1, output);
        }
    }

    fclose(output);
    fclose(input);

    //clock_t end = clock();
    //double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    //tot_flip_coins += elapsed_secs;

    return output_name;
}

struct NodeNext {
    unsigned int key;
    unsigned int next;
    unsigned int next_next;
    NodeNext() {};
    NodeNext(unsigned int k, unsigned int nx, unsigned int nx_nx) :
        key(k), next(nx), next_next(nx_nx) {};
    bool operator < (const NodeNext& other) const {
        return key < other.key;
    }
};

struct NodeNextW1 : NodeNext {
    unsigned int w1;
    NodeNextW1() {};
    NodeNextW1(unsigned int a,
        unsigned int b,
        unsigned int c,
        unsigned int ww1) : NodeNext(a, b, c), w1(ww1) {};
};

struct NodeNextW1F1 : NodeNextW1 {
    unsigned int f1;
    NodeNextW1F1() {};
    NodeNextW1F1(unsigned int a,
        unsigned int b,
        unsigned int c,
        unsigned int w1,
        unsigned int ff1) : NodeNextW1(a, b, c, w1), f1(ff1) {};
};

struct NodeNextW2F1 : NodeNextW1F1 {
    unsigned int w2;
    NodeNextW2F1() {};
    NodeNextW2F1(unsigned int a,
        unsigned int b,
        unsigned int c,
        unsigned int w1,
        unsigned int f1,
        unsigned int ww2) : NodeNextW1F1(a, b, c, w1, f1), w2(ww2) {};
};

struct NodeNextW2F2 : NodeNextW2F1 {
    unsigned int f2;
    NodeNextW2F2() {};
    NodeNextW2F2(unsigned int a,
        unsigned int b,
        unsigned int c,
        unsigned int w1,
        unsigned int f1,
        unsigned int w2,
        unsigned int ff2) : NodeNextW2F1(a, b, c, w1, f1, w2), f2(ff2) {};
};

struct NodeNextW2F3 : NodeNextW2F2 {
    unsigned int f3;
    NodeNextW2F3() {};
    NodeNextW2F3(unsigned int a,
        unsigned int b,
        unsigned int c,
        unsigned int w1,
        unsigned int f1,
        unsigned int w2,
        unsigned int f2,
        unsigned int ff3) : NodeNextW2F2(a, b, c, w1, f1, w2, f2), f3(ff3) {};
};

struct NodeNextW3F3 : NodeNextW2F3 {
    unsigned int w3;
    NodeNextW3F3() {};
    NodeNextW3F3(unsigned int a,
        unsigned int b,
        unsigned int c,
        unsigned int w1,
        unsigned int f1,
        unsigned int w2,
        unsigned int f2,
        unsigned int f3,
        unsigned int ww3) : NodeNextW2F3(a, b, c, w1, f1, w2, f2, f3), w3(ww3) {};
};

void do_simple_ranking(const char* input_now, const char* weights_now, const char* output_name, unsigned int n) {
    FILE* input = fopen(input_now, "rb");
    FILE* output = fopen(output_name, "wb");
    FILE* weights_file = fopen(weights_now, "rb");

    Link* links = (Link*)gl_buf;
    NodeWeight* weights = (NodeWeight*)(gl_buf + n * sizeof(Link));

    fread(links, sizeof(Link), n, input);
    sort(links, links + n);

    fread(weights, sizeof(NodeWeight), n, weights_file);

    unsigned int now = links[0].key, ranking = 0;
    for (int i = 0; i < n; i++) {
        auto it_w = lower_bound(weights, weights + n, NodeWeight(now, 0));
        ranking += it_w->weight;

        Link cur(now, ranking);
        fwrite(&cur, sizeof(Link), 1, output);
        auto it = lower_bound(links, links + n, Link(now, 0));
        now = it->next;
    }

    fclose(input);
    fclose(output);
    fclose(weights_file);
}

tuple<Filename, Filename, Filename, unsigned int> make_new_graph(const char* input_name, int old_n) {
    FILE* input = fopen(input_name, "rb");
    const int block_sz = ALL_BYTES / (sizeof(NodeNextW3F3) + sizeof(Link) + sizeof(Link) + sizeof(NodeWeight));

    NodeNextW3F3* sbuf = (NodeNextW3F3*)gl_buf;
    Link* output_buf = (Link*)(gl_buf + block_sz * sizeof(NodeNextW3F3));
    Link* removed_edges_buf = (Link*)(gl_buf + block_sz * (sizeof(NodeNextW3F3) + sizeof(Link)));
    NodeWeight* new_weights_buf = (NodeWeight*)(gl_buf + block_sz * (sizeof(NodeNextW3F3) + sizeof(Link) + sizeof(Link)));

    int output_buf_cnt = 0, removed_edges_cnt = 0, new_weights_cnt = 0;
    int new_n = old_n;

    Filename new_graph = get_filename(old_n, "graph_from");
    FILE* output = fopen(new_graph.c_str(), "wb");
    //setvbuf(output, NULL, _IONBF, BUFSIZ);

    Filename removed_ed_name = get_filename(old_n, "removed_ed");
    FILE* removed_edges = fopen(removed_ed_name.c_str(), "wb");
    //setvbuf(removed_edges, NULL, _IONBF, BUFSIZ);

    Filename new_weights_name = get_filename(old_n, "new_weights");
    FILE* new_weights = fopen(new_weights_name.c_str(), "wb");
    //setvbuf(new_weights, NULL, _IONBF, BUFSIZ);

    //exit(0);
    for (int i = 0; i < old_n; i += block_sz) {
        int sz = min(block_sz, old_n - i);
        fread(sbuf, sizeof(NodeNextW3F3), sz, input);
        for (int j = 0; j < sz; j++) {
            NodeNextW3F3 &cur = sbuf[j];
            // i n(i) n(n(i)) w(i) f(i) w(n(i)) f(n(i)) f(n(n(i)))
            //cerr << cur.key << " " << cur.next << " " << cur.next_next << " " << cur.w1 << " "
            //   << cur.f1 << " " << cur.w2 << " " << cur.f2 << " " << cur.f3 << endl;

            // considering what happens to n(i) - n(n(i)) edge
            // i == 1 and n(i) == 0 -> remove n(i)
            if (cur.f1 == 1 && cur.f2 == 0) {
                Link edge(cur.key, cur.next_next);
                //cerr << "remove and next" << cur.key << " " << cur.next_next << endl;
                output_buf[output_buf_cnt++] = edge;
                if (output_buf_cnt == block_sz) {
                    fwrite(output_buf, sizeof(Link), output_buf_cnt, output);
                    output_buf_cnt = 0;
                }

                //fwrite(&edge, sizeof(Link), 1, output);
                new_n--;

                Link removed_edge(cur.key, cur.next);
                //cerr << "removed edge " << cur.key << " " << cur.next << endl;

                removed_edges_buf[removed_edges_cnt++] = removed_edge;
                if (removed_edges_cnt == block_sz) {
                    fwrite(removed_edges_buf, sizeof(Link), removed_edges_cnt, removed_edges);
                    removed_edges_cnt = 0;
                }
                //fwrite(&removed_edge, sizeof(Link), 1, removed_edges);
            }
            else {
                // n(i) -> n(n(i)) will exist
                if (!(cur.f2 == 1 && cur.f3 == 0)) {
                    //cerr << "save " << cur.next << " " << cur.next_next << endl;
                    Link edge(cur.next, cur.next_next);
                    output_buf[output_buf_cnt++] = edge;
                    if (output_buf_cnt == block_sz) {
                        fwrite(output_buf, sizeof(Link), output_buf_cnt, output);
                        output_buf_cnt = 0;
                    }
                    //fwrite(&edge, sizeof(Link), 1, output);

                    NodeWeight new_w(cur.next, cur.w2);

                    new_weights_buf[new_weights_cnt++] = new_w;
                    if (new_weights_cnt == block_sz) {
                        fwrite(new_weights_buf, sizeof(NodeWeight), new_weights_cnt, new_weights);
                        new_weights_cnt = 0;
                    }
                    //fwrite(&new_w, sizeof(NodeWeight), 1, new_weights);
                }
                else {
                    NodeWeight new_w(cur.next, cur.w2 + cur.w3);

                    new_weights_buf[new_weights_cnt++] = new_w;
                    if (new_weights_cnt == block_sz) {
                        fwrite(new_weights_buf, sizeof(NodeWeight), new_weights_cnt, new_weights);
                        new_weights_cnt = 0;
                    }
                    //fwrite(&new_w, sizeof(NodeWeight), 1, new_weights);
                }
            }
        }
    }

    if (output_buf_cnt > 0) {
        fwrite(output_buf, sizeof(Link), output_buf_cnt, output);
        output_buf_cnt = 0;
    }

    if (removed_edges_cnt > 0) {
        fwrite(removed_edges_buf, sizeof(Link), removed_edges_cnt, removed_edges);
        removed_edges_cnt = 0;
    }

    if (new_weights_cnt > 0) {
        fwrite(new_weights_buf, sizeof(NodeWeight), new_weights_cnt, new_weights);
        new_weights_cnt = 0;
    }

    fclose(input);
    fclose(output);
    fclose(removed_edges);
    fclose(new_weights);

    assert(new_n < old_n);
    Filename sorted_new_weights = ext_sort<NodeWeight>(0, new_n - 1, 0, new_weights_name.c_str(), 0);

    remove(new_weights_name.c_str());
    return make_tuple(move(new_graph), move(removed_ed_name), move(sorted_new_weights), new_n);

}


void copy_file(FILE* to, const char* from) {
    FILE* file_to_read = fopen(from, "rb");
    unsigned char* sbuf = gl_buf;

    while (true) {
        int sz = fread(sbuf, 1, ALL_BYTES, file_to_read);
        if (sz <= 0) {
            break;
        }
        fwrite(sbuf, 1, sz, to);
    }
    fclose(file_to_read);
}

void concat_files(const char* file_to, const char* file_add_A, const char* file_add_B) {
    FILE* file_to_write = fopen(file_to, "wb");
    copy_file(file_to_write, file_add_A);
    copy_file(file_to_write, file_add_B);
    fclose(file_to_write);
}

Filename list_rank(const char* input_now, const char* weights_now, int n) {
    Filename result = get_filename(n, "raw_ranking");
    if (n < ALL_BYTES / (sizeof(Link) + sizeof(NodeWeight))) {
        do_simple_ranking(input_now, weights_now, result.c_str(), n);
        return result;
    }
    tuple<Filename, Filename, Filename> sorted_next_next = next_next(input_now, n);
    Filename next_next_file = get_filename(n, "next_nnext");
    join<Link, Link, NodeNext>(get<0>(sorted_next_next).c_str(),
        get<2>(sorted_next_next).c_str(),
        next_next_file.c_str(),
        [](const Link& next, const Link& next_next) -> NodeNext {
        // i n(i) n(n(i))
        return NodeNext(next.key, next.next, next_next.next);
    }
    );

    remove(get<0>(sorted_next_next).c_str());
    remove(get<1>(sorted_next_next).c_str());
    remove(get<2>(sorted_next_next).c_str());

    Filename coins = flip_coins(input_now, n);
    Filename sorted_coins = ext_sort<Link>(0, n - 1, 0, coins.c_str(), 0);

    remove(coins.c_str());

    Filename next_next_w1 = get_filename(n, "next_w1");
    join<NodeNext, NodeWeight, NodeNextW1>(next_next_file.c_str(),
        weights_now,
        next_next_w1.c_str(),
        [](const NodeNext& A, const NodeWeight& B) -> NodeNextW1 {
        // i n(i) n(n(i)) w(i)
        return NodeNextW1(A.key, A.next, A.next_next, B.weight);
    }
    );

    remove(next_next_file.c_str());

    Filename next_next_w1_f1 = get_filename(n, "next_w1_f1");
    join<NodeNextW1, Link, NodeNextW1F1>(next_next_w1.c_str(),
        sorted_coins.c_str(),
        next_next_w1_f1.c_str(),
        [](const NodeNextW1& A, const Link& B) -> NodeNextW1F1 {
        // n(i) i n(n(i)) w(i) f(i)
        return NodeNextW1F1(A.next, A.key, A.next_next, A.w1, B.next);
    }
    );
    Filename sorted_next_next_w1_f1 = ext_sort<NodeNextW1F1>(0, n - 1, 0, next_next_w1_f1.c_str(), 0);

    remove(next_next_w1.c_str());
    remove(next_next_w1_f1.c_str());

    Filename next_next_w2_f1 = get_filename(n, "next_w2_f1");
    join<NodeNextW1F1, NodeWeight, NodeNextW2F1>(sorted_next_next_w1_f1.c_str(),
        weights_now,
        next_next_w2_f1.c_str(),
        [](const NodeNextW1F1& A, const NodeWeight& B) -> NodeNextW2F1 {
        // n(i) i n(n(i)) w(i) f(i) w(n(i))
        return NodeNextW2F1(A.key, A.next, A.next_next, A.w1, A.f1, B.weight);
    }
    );

    remove(sorted_next_next_w1_f1.c_str());

    Filename next_next_w2_f2 = get_filename(n, "next_w2_f2");
    join<NodeNextW2F1, Link, NodeNextW2F2>(next_next_w2_f1.c_str(),
        sorted_coins.c_str(),
        next_next_w2_f2.c_str(),
        [](const NodeNextW2F1& A, const Link& B) -> NodeNextW2F2 {
        // n(n(i)) i n(i) w(i) f(i) w(n(i)) f(n(i))
        return NodeNextW2F2(A.next_next, A.next, A.key, A.w1, A.f1, A.w2, B.next);
    }
    );
    Filename sorted_next_next_w2_f2 = ext_sort<NodeNextW2F2>(0, n - 1, 0, next_next_w2_f2.c_str(), 0);

    remove(next_next_w2_f1.c_str());
    remove(next_next_w2_f2.c_str());

    Filename next_next_w2_f3 = get_filename(n, "next_w2_f3");
    join<NodeNextW2F2, Link, NodeNextW2F3>(sorted_next_next_w2_f2.c_str(),
        sorted_coins.c_str(),
        next_next_w2_f3.c_str(),
        [](const NodeNextW2F2& A, const Link& B) -> NodeNextW2F3 {
        // n(n(i)) i n(i) w(i) f(i) w(n(i)) f(n(i)) f(n(n(i)))
        return NodeNextW2F3(A.key, A.next, A.next_next, A.w1, A.f1, A.w2, A.f2, B.next);
    }
    );

    remove(sorted_coins.c_str());
    remove(sorted_next_next_w2_f2.c_str());

    Filename next_next_w3_f3 = get_filename(n, "next_w3_f3");
    join<NodeNextW2F3, NodeWeight, NodeNextW3F3>(next_next_w2_f3.c_str(),
        weights_now,
        next_next_w3_f3.c_str(),
        [](const NodeNextW2F3& A, const NodeWeight& B) -> NodeNextW3F3 {
        // i n(i) n(n(i)) w(i) f(i) w(n(i)) f(n(i)) f(n(n(i))) w(n(n(i)))
        return NodeNextW3F3(A.next, A.next_next, A.key, A.w1, A.f1, A.w2, A.f2, A.f3, B.weight);
    }
    );

    remove(next_next_w2_f3.c_str());

    tuple<Filename, Filename, Filename, int> new_graph_n = make_new_graph(next_next_w3_f3.c_str(), n);

    remove(next_next_w3_f3.c_str());

    Filename new_graph_filename = move(get<0>(new_graph_n));
    Filename removed_edges_filename = move(get<1>(new_graph_n));
    Filename new_weights_filename = move(get<2>(new_graph_n));
    unsigned int new_n = get<3>(new_graph_n);

    unsigned int num_removed_edges = n - new_n;

    Filename sorted_removed_edges = ext_sort<Link>(0, num_removed_edges - 1, 0, removed_edges_filename.c_str(), 0);

    Filename rec_result = list_rank(new_graph_filename.c_str(), new_weights_filename.c_str(), new_n);
    Filename sorted_rec_result = ext_sort<NodeWeight>(0, new_n - 1, 0, rec_result.c_str(), 0);

    Filename rankes_minus_new = get_filename(new_n, "rankes_minus_new");
    join<NodeWeight, NodeWeight, NodeWeight>(sorted_rec_result.c_str(),
        new_weights_filename.c_str(),
        rankes_minus_new.c_str(),
        [](const NodeWeight& A, const NodeWeight& B) -> NodeWeight {
        return NodeWeight(A.key, A.weight - B.weight);
    }
    );

    Filename rankes_actual_new = get_filename(new_n, "rankes_act_n");
    join<NodeWeight, NodeWeight, NodeWeight>(rankes_minus_new.c_str(),
        weights_now,
        rankes_actual_new.c_str(),
        [](const NodeWeight& A, const NodeWeight& B) -> NodeWeight {
        return NodeWeight(A.key, A.weight + B.weight);
    }
    );

    Filename rankes_removed_r = get_filename(new_n, "rankes_removed_r");

    join<NodeWeight, Link, NodeWeight>(rankes_actual_new.c_str(),
        sorted_removed_edges.c_str(),
        rankes_removed_r.c_str(),
        [](const NodeWeight& A, const Link& B) -> NodeWeight {
        return NodeWeight(B.next, A.weight);
    }
    );

    Filename sorted_rankes_removed_r = ext_sort<NodeWeight>(0, num_removed_edges - 1, 0, rankes_removed_r.c_str(), 0);

    Filename removed_rankes = get_filename(new_n, "removed_rankes");
    join<NodeWeight, NodeWeight, NodeWeight>(sorted_rankes_removed_r.c_str(),
        weights_now,
        removed_rankes.c_str(),
        [](const NodeWeight& A, const NodeWeight& B) -> NodeWeight {
        return NodeWeight(A.key, A.weight + B.weight);
    }
    );

    concat_files(result.c_str(), rankes_actual_new.c_str(), removed_rankes.c_str());

    return result;
}


void transform_to_outputbin(const char* input_name, const char* to, int n) {
    FILE* input = fopen(input_name, "rb");

    Filename rank_key_name = get_filename(n, "rank_key");
    FILE* rank_key = fopen(rank_key_name.c_str(), "wb");

    // Link contains key - rank
    Link* sbuf = (Link*)gl_buf;
    for (int i = 0; i < n; i += BLOCK) {
        int sz = min(BLOCK, n - i);
        fread(sbuf, sizeof(Link), sz, input);
        for (int j = 0; j < sz; j++) {
            swap(sbuf[j].key, sbuf[j].next);
        }
        fwrite(sbuf, sizeof(Link), sz, rank_key);
    }
    fclose(input);
    fclose(rank_key);

    Filename sorted_rank_key = ext_sort<Link>(0, n - 1, 0, rank_key_name.c_str(), 0);

    rank_key = fopen(sorted_rank_key.c_str(), "rb");
    FILE* output_bin = fopen(to, "wb");

    unsigned int min_element = 1 << 30;
    //unsigned int min_element = (((unsigned int)1 << 31) - 1) + ((unsigned int)1 << 31);
    int min_element_pos;
    for (int i = 0; i < n; i += BLOCK) {
        int sz = min(BLOCK, n - i);
        fread(sbuf, sizeof(Link), sz, rank_key);
        for (int j = 0; j < sz; j++) {
            if (sbuf[j].next < min_element) {
                min_element = sbuf[j].next;
                min_element_pos = i + j;
            }
        }
    }

    unsigned int* qbuf = (unsigned int*)gl_buf;

    fseek(rank_key, min_element_pos * sizeof(Link), SEEK_SET);
    for (int i = min_element_pos; i < n; i += BLOCK) {
        int sz = min(BLOCK, n - i);
        fread(sbuf, sizeof(Link), sz, rank_key);

        for (int j = 0; j < sz; j++) {
            qbuf[j] = sbuf[j].next;
        }
        fwrite(qbuf, 4, sz, output_bin);
    }

    fseek(rank_key, 0, SEEK_SET);
    for (int i = 0; i < min_element_pos; i += BLOCK) {
        int sz = min(BLOCK, min_element_pos - i);
        fread(sbuf, sizeof(Link), sz, rank_key);

        for (int j = 0; j < sz; j++) {
            qbuf[j] = sbuf[j].next;
        }
        fwrite(qbuf, 4, sz, output_bin);
    }

    fclose(rank_key);
    fclose(output_bin);
}

void transform_sort_to_irunner(const char* filename, unsigned long long n) {
    FILE* input = fopen(filename, "rb");
    FILE* output = fopen("output.bin", "wb");
    fwrite(&n, 8, 1, output);
    unsigned long long sbuf[BLOCK];
    int sz = -1;
    while (true) {
        sz = fread(sbuf, 8, BLOCK, input);
        if (sz <= 0) {
            break;
        }
        fwrite(sbuf, 8, sz, output);
    }
    fclose(input);
    fclose(output);
}

Filename do_list_ranking(const char* input, const char* to, unsigned int n) {
    Filename init_weights_file = prepare_weights(input, n);
    Filename solution = list_rank(input, init_weights_file.c_str(), n);

    transform_to_outputbin(solution.c_str(), to, n);
}

struct EdgeType {
    unsigned ;int from;
    unsigned int to;
    unsigned int type;
    unsigned int id;
    EdgeType() {};
    EdgeType(unsigned int a, unsigned int b, unsigned int c, unsigned int d) {
        from = a;
        to = b;
        type = c;
        id = d;
    }
    bool operator < (const EdgeType &other) const {
        if (from != other.from) {
            return from < other.from;
        }
        if (type >= 2 && other.type >= 2) {
            return to < other.to;
        }
        if (type != other.type) {
            return type < other.type;
        }
        return to < other.to;
    }
};

struct EdgeId {
    unsigned int from;
    unsigned int to;
    unsigned int id;
    EdgeType() {};
    EdgeType(unsigned int a, unsigned int b, unsigned int c) {
        from = a;
        to = b;
        id = c;
    }

    bool operator < (const EdgeType &other) const {
        if (from != other.from) {
            return from < other.from;
        }
        return to < other.to;
    }
};

void prepare_type_edges(const char* filename, const char* to, unsigned int n) {
    FILE* input = fopen(filename, "rb");
    FILE* output = fopen(to, "wb");

    Link sbuf[BLOCK];
    int sz = -1;
    unsigned int tot_edges = 0;
    while (true) {
        sz = fread(sbuf, sizeof(Link), BLOCK, input);
        if (sz <= 0) {
            break;
        }
        for (int i = 0; i < sz; i++) {
            unsigned int from = sbuf[i].key;
            unsigned int to = sbuf[i].to;

            direct_edge_id = tot_edges++;
            reverse_edge_id = tot_edges++;

            EdgeType from_to(from, to, 100, direct_edge_id);
            EdgeType to_from(to, from, 100, reverse_edge_id);

            from_to.type = 2
            fwrite(&from_to, sizeof(EdgeType), 1, output);


        }

    }
    fclose(input);
    fclose(output);
}


int main() {
    //srand(2327);
    //srand(2341);
    //srand(time(NULL));
    clock_t beg_prep = clock();
    prepare_file();
    //prepate_file_for_sort();


    //prepare_file_without_memory();
    clock_t end_prep = clock();

    //cerr << "prepared in " << double(end_prep - beg_prep) / CLOCKS_PER_SEC << endl;

    clock_t begin = clock();
    const char* input_normal_name = "input_normal.bin";
    unsigned int n;

    FILE* input = fopen("input.bin", "rb");
    fread(&n, 4, 1, input);
    transform_file_from_irunner(input, input_normal_name, n - 1);
    //check_file(input_normal_name, 2);
    fclose(input);

    prepare_type_edges(input_normal_name, "type_edges", n - 1);
    //do_list_ranking(input_normal_name, "ranking.bin", n);


    //check_file("output.bin");
    //check_file("ranking.bin");





    clock_t end = clock();
    double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    //cout << "total time: " << elapsed_secs << endl;
    //cout << "total sort time: " << tot_sort_time << endl;
    //cout << "total join time: " << tot_join_time << endl;
    //cout << "total flip coins: " << tot_flip_coins << endl;

    //check_output();
    return 0;
}