#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 prepare_file_test() {
   FILE* input = fopen("input.bin", "wb");
   //vector<unsigned int> v{4, 1, 2, 2, 3, 2, 4};
   //vector<unsigned int> v{4, 2, 3, 2, 1, 4, 2};
   //vector<unsigned int> v{4, 3, 2, 3, 1, 3, 4};
   //vector<unsigned int> v{4, 3, 2, 4, 1, 2, 4};
   /*vector<unsigned int> v{6, 5,
                            1, 2,
                            2, 3,
                            3, 4,
                            2, 5,
                            3, 5,
                            5,
                            1, 6,
                            2, 3,
                            1, 4,
                            4, 5,
                            1, 4,
                            1, 4};*/
   /*vector<unsigned int> v{10, 11,
                            1, 8,
                            7, 1,
                            8, 2,
                            7, 8,
                            3, 4,
                            3, 5,
                            3, 6,
                            3, 10,
                            4, 5,
                            4, 10,
                            5, 6,

                            5,
                            1, 6,
                            2, 3,
                            5, 10,
                            1, 2,
                            5, 4,
                            };*/
   vector<unsigned int> v{4, 3,
                            1, 3,
                            4, 2,
                            4, 3,
                            3,
                            1, 2,
                            1, 4,
                            2, 3,
                            };
   fwrite(&v[0], sizeof(unsigned int), v.size(), input);
   fclose(input);
}

void check_file(const char* filename, int ln = 1) {
    cerr << "---" << endl;
    cerr << filename << endl;
    FILE* input = fopen(filename, "rb");
    int cur;
    //unsigned long long cur;
    int cnt = 0;
    while (fread(&cur, 4, 1, input)) {
        cerr << 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 {
        if (key != A.key)
            return key < A.key;
        return next < A.next;
    }
    //~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++;
            sz_output++; 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;
}





pair<Filename, Filename> transform_input_from_irunner(const char* input_name, int& n, int& new_m, int& queries) {
    FILE* input = fopen(input_name, "rb");

    int m;
    fread(&n, 4, 1, input);
    fread(&m, 4, 1, input);

    Filename edges_input_name = get_filename(m, "edges_input");
    FILE* edges_input = fopen(edges_input_name.c_str(), "wb");

    Link sbuf[BLOCK];
    new_m = 0;

    for (int i = 0; i < m; i += BLOCK) {
        int sz = min(BLOCK, m - i);
        fread(sbuf, sizeof(Link), sz, input);
        for (int j = 0; j < sz; j++) {
            if (sbuf[j].key != sbuf[j].next) {
                new_m++;
                fwrite(&sbuf[j], sizeof(Link), 1, edges_input);
                new_m++;
                swap(sbuf[j].key, sbuf[j].next);
                fwrite(&sbuf[j], sizeof(Link), 1, edges_input);
            }
        }
    }


    fread(&queries, 4, 1, input);
    Filename queries_input_name = get_filename(queries, "queries_input");
    FILE* queries_input = fopen(queries_input_name.c_str(), "wb");
    for (int i = 0; i < queries; i += BLOCK) {
        int sz = min(BLOCK, queries - i);
        fread(sbuf, sizeof(Link), sz, input);
        fwrite(sbuf, sizeof(Link), sz, queries_input);
    }

    fclose(input);
    fclose(edges_input);
    fclose(queries_input);

    return make_pair(edges_input_name, queries_input_name);
}

Filename choose_min_outcome(const char* edges_input_name, int m, int& out_m) {
    FILE* input = fopen(edges_input_name, "rb");

    Filename min_outcome_name = get_filename(m, "to_who");
    FILE* min_outcome = fopen(min_outcome_name.c_str(), "wb");

    int prev_ver = 1234567;
    out_m = 0;
    Link sbuf[BLOCK];
    for (int i = 0; i < m; i += BLOCK) {
        int sz = min(BLOCK, m - i);
        fread(sbuf, sizeof(Link), sz, input);

        for (int j = 0; j < sz; j++) {
            if (prev_ver != sbuf[j].key) {
                prev_ver = sbuf[j].key;
                out_m++;
                fwrite(&sbuf[j], sizeof(Link), 1, min_outcome);
            }
        }
    }

    fclose(input);
    fclose(min_outcome);

    return min_outcome_name;
}

Filename inverse_edges(const char* input_name, int m) {
    FILE* input = fopen(input_name, "rb");
    Filename output_name = get_filename(m, "inversed_edges");
    FILE* output = fopen(output_name.c_str(), "wb");

    Link sbuf[BLOCK];

    for (int i = 0; i < m; i += BLOCK) {
        int sz = min(BLOCK, m - 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, output);
    }

    fclose(input);
    fclose(output);
    return output_name;
}

struct NextNext {
    unsigned int key;
    unsigned int prev;
    unsigned int next;
    NextNext() {};
    NextNext(unsigned int a, unsigned int b, unsigned int c): key(a), prev(b), next(c) {};
};

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);
}

Filename remove_cycle(const char* input_name, int m_now, int& acycle_m, FILE* global_prev, int& added_prevs) {
    FILE* input = fopen(input_name, "rb");
    Filename output_name = get_filename(m_now, "acycle");

    FILE* output = fopen(output_name.c_str(), "wb");

    acycle_m = 0;

    NextNext sbuf[BLOCK];
    Link out;
    for (int i = 0; i < m_now; i += BLOCK) {
        int sz = min(BLOCK, m_now - i);
        fread(sbuf, sizeof(NextNext), sz, input);
        for (int j = 0; j < sz; j++) {
            if (sbuf[j].prev != sbuf[j].next || sbuf[j].prev > sbuf[j].key) {
                out = Link(sbuf[j].prev, sbuf[j].key);
                acycle_m++;
                added_prevs++;
                fwrite(&out, sizeof(Link), 1, output);
                fwrite(&out, sizeof(Link), 1, global_prev);
            }


            if (sbuf[j].prev == sbuf[j].next && sbuf[j].key < sbuf[j].prev) {
                Link root_color(sbuf[j].key, sbuf[j].key);
                acycle_m++;
                fwrite(&root_color, sizeof(Link), 1, output);
            }
        }

    }

    fclose(input);
    fclose(output);

    return output_name;
}


Filename shrink_graph(const char* edges_now, int m) {
    Filename sorted_edges_now = ext_sort<Link>(0, m - 1, 0, edges_now, 0);
    Filename inversed_edges = inverse_edges(sorted_edges_now.c_str(), m);
    Filename sorted_inversed_edges = ext_sort<Link>(0, m - 1, 0, inversed_edges.c_str(), 0);

    Filename next_next = get_filename(m, "next_next_sh");
    join<Link, Link, NextNext>(sorted_edges_now.c_str(),
                               sorted_inversed_edges.c_str(),
                               next_next.c_str(),
                               [] (const Link& A, const Link& B) -> NextNext {
                                    return NextNext(A.key, B.next, A.next);
                               }
                               );

    check_file(next_next.c_str(), 3);

    int changes = 0;
    NextNext sbuf[BLOCK];

    Filename new_prevs_name = get_filename(m, "new_prevs");
    FILE* input = fopen(next_next.c_str(), "rb");
    FILE* new_prevs = fopen(new_prevs_name.c_str(), "wb");

    Link out;

    for (int i = 0; i < m; i += BLOCK) {
        int sz = min(BLOCK, m - i);
        fread(sbuf, sizeof(NextNext), sz, input);
        for (int j = 0; j < sz; j++) {
            out = Link(sbuf[j].prev, sbuf[j].next);
            fwrite(&out, sizeof(Link), 1, new_prevs);
            changes += sbuf[j].key != sbuf[j].next;
        }
    }

    fclose(new_prevs);
    fclose(input);
    cerr << "changes " << changes << endl;
    check_file(new_prevs_name.c_str(), 2);

    if (changes == 0) {
        return sorted_edges_now;
    }
    else {
        return shrink_graph(new_prevs_name.c_str(), m);
    }
}

struct EdgeC1 : Link {
    unsigned int c1;
    EdgeC1() {};
    EdgeC1(unsigned int a,
           unsigned int b,
           unsigned int c) : Link(a, b), c1(c) {};
};

struct  EdgeC2: EdgeC1 {
    unsigned int c2;
    EdgeC2() {};
    EdgeC2(unsigned int a,
           unsigned int b,
           unsigned int c,
           unsigned int d) : EdgeC1(a, b, c), c2(d) {};

};

Filename make_new_edges(const char* edges_now, const char* colors, int m, int& new_m) {
    cerr << "make_new_edges" << endl;
    check_file(edges_now, 2);
    check_file(colors, 2);

    Filename edges_c1 = get_filename(m, "edges_c1");
    join<Link, Link, EdgeC1>(colors,
                             edges_now,
                             edges_c1.c_str(),
                             [] (const Link& A, const Link& B) -> EdgeC1 {
                                 return EdgeC1(B.next, B.key, A.next);
                             }
                             );

    check_file(edges_c1.c_str(), 3);
    Filename sorted_edges_c1 = ext_sort<EdgeC1>(0, m - 1, 0, edges_c1.c_str(), 0);

    Filename edges_c2 = get_filename(m, "edges_c2");
    join<Link, EdgeC1, EdgeC2>(colors,
                               sorted_edges_c1.c_str(),
                               edges_c2.c_str(),
                               [] (const Link& A, const EdgeC1& B) -> EdgeC2 {
                                   return EdgeC2(B.next, B.key, B.c1, A.next);
                               }
                               );

    check_file(edges_c2.c_str(), 4);

    FILE* edges_c2_file = fopen(edges_c2.c_str(), "rb");

    Filename new_graph_name = get_filename(m, "new_gr_sh");
    new_m = 0;

    FILE* new_graph = fopen(new_graph_name.c_str(), "wb");
    cerr << "m: " << m << endl;
    EdgeC2 sbuf[BLOCK];
    for (int i = 0; i < m; i += BLOCK) {
        int sz = min(BLOCK, m - i);
        fread(sbuf, sizeof(EdgeC2), sz, edges_c2_file);

        for (int j = 0; j < sz; j++) {
            if (sbuf[j].c1 == sbuf[j].c2) {
                continue;
            }
            Link out(sbuf[j].c1, sbuf[j].c2);
            new_m++;
            fwrite(&out, sizeof(Link), 1, new_graph);
        }
    }

    fclose(new_graph);
    fclose(edges_c2_file);
    cerr << "new_m " << new_m << endl;
    check_file(new_graph_name.c_str(), 2);
    return new_graph_name;
}

void find_prevs(const char* edges_input_name, int m, FILE* global_prev, int& added_prevs) {
    if (m == 0) {
        return ;
    }

    int out_m;
    Filename to_who = choose_min_outcome(edges_input_name, m, out_m);
    cerr << out_m << endl;
    check_file(to_who.c_str(), 2);

    Filename inversed_edges = inverse_edges(to_who.c_str(), out_m);
    check_file(inversed_edges.c_str(), 2);

    Filename sorted_inversed_edges = ext_sort<Link>(0, out_m - 1, 0, inversed_edges.c_str(), 0);
    check_file(sorted_inversed_edges.c_str(), 2);

    Filename next_next = get_filename(m, "next_next_cr");
    join<Link, Link, NextNext>(to_who.c_str(),
                               sorted_inversed_edges.c_str(),
                               next_next.c_str(),
                               [] (const Link& A, const Link& B) -> NextNext {
                                    return NextNext(A.key, B.next, A.next);
                               }
                               );
    check_file(next_next.c_str(), 3);


    int acycle_m;
    Filename prevs_now = remove_cycle(next_next.c_str(), out_m, acycle_m, global_prev, added_prevs);

    cerr << "acycle_m " << acycle_m << endl;
    check_file(prevs_now.c_str(), 2);


    Filename colors_name = shrink_graph(prevs_now.c_str(), acycle_m);
    cerr << "colors " << endl;
    check_file(colors_name.c_str(), 2);

    int new_m;
    Filename new_edges = make_new_edges(edges_input_name, colors_name.c_str(), m, new_m);

    if (new_m == 0) {
        return ;
    }
    Filename sorted_new_edges = ext_sort<Link>(0, new_m - 1, 0, new_edges.c_str(), 0);
    find_prevs(sorted_new_edges.c_str(), new_m, global_prev, added_prevs);
}

Filename add_roots(const char* global_now, int n, int added_prevs) {
    Filename sorted_global = ext_sort<Link>(0, added_prevs - 1, 0, global_now, 0);
    Link sbuf[BLOCK];

    Filename all_prevs_name = get_filename(n, "all_prevs");

    FILE* input = fopen(sorted_global.c_str(), "rb");
    FILE* all_prevs = fopen(all_prevs_name.c_str(), "wb");

    Link cur(0, 0);
    Link out;
    bool ignore = false;
    for (int i = 1; i <= n; i++) {
        if (i > cur.key && !ignore) {
            int sz = fread(&cur, sizeof(Link), 1, input);
            if (sz == 0) {
                ignore = true;
            }
        }
        if (!ignore && i == cur.key) {
            fwrite(&cur, sizeof(Link), 1, all_prevs);
        }
        else {
            out = Link(i, i);
            fwrite(&out, sizeof(Link), 1, all_prevs);
        }
    }

    fclose(all_prevs);
    fclose(input);
    return all_prevs_name;
}


int traverse(int start, unsigned int* to, FILE* prevs) {
    int len = 0;
    Link cur;
    while (true) {
        cerr << start << endl;
        to[len++] = start;
        fseek(prevs, sizeof(Link) * (start - 1), SEEK_SET);
        fread(&cur, sizeof(Link), 1, prevs);
        if (cur.next == start) {
            break;
        }
        start = cur.next;
    }
    return len;
}

void answer_queries(const char* queries_input_name, int q, const char* global_prevs) {
    FILE* prevs = fopen(global_prevs, "rb");
    FILE* queries = fopen(queries_input_name, "rb");
    FILE* output = fopen("output.bin", "wb");
    Link query;

    unsigned int sbuf[BLOCK];
    unsigned int qbuf[BLOCK];
    int root1, root2;
    for (int it = 0; it < q; it++) {
        fread(&query, sizeof(Link), 1, queries);
        cerr << "query: " << query.key << " " << query.next << endl;
        int len1 = traverse(query.key, sbuf, prevs);
        int len2 = traverse(query.next, qbuf, prevs);
        if (sbuf[len1 - 1] != qbuf[len2 -1]) {
            int minus_one = -1;
            cerr << "minus_one" << endl;
            fwrite(&minus_one, sizeof(int), 1, output);
        }
        else {
            int tot_len = len1 + len2 - 1;
            fwrite(&tot_len, sizeof(int), 1, output);
            cerr << "len: " << tot_len << endl;
            for (int i = 0; i < len1; i++) {
                fwrite(&sbuf[i], sizeof(int), 1, output);
                cerr << "out: " << sbuf[i] << endl;
            }
            for (int i = len2 - 2; i >= 0; i--) {
                fwrite(&qbuf[i], sizeof(int), 1, output);
                cerr << "out: " << qbuf[i] << endl;
            }
        }
    }

    fclose(prevs);
    fclose(queries);
    fclose(output);
}

int main() {

    //srand(2327);
    //srand(2341);
    //srand(time(NULL));
    clock_t beg_prep = clock();

    prepare_file_test();
    check_file("input.bin");

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

    int n, m, q;
    pair<Filename, Filename> transformed_inputs = transform_input_from_irunner("input.bin", n, m, q);
    cerr << n << " " << m << " " << q << endl;
    //check_file(transformed_inputs.first.c_str(), 2);
    //check_file(transformed_inputs.second.c_str(), 2);

    Filename sorted_edges = ext_sort<Link>(0, m - 1, 0, transformed_inputs.first.c_str(), 0);
    check_file(sorted_edges.c_str(), 2);


    //cerr << "prepared in " << double(end_prep - beg_prep) / CLOCKS_PER_SEC << endl;
    Filename global_prev_name = get_filename(m, "global_prev");
    FILE* global_prev = fopen(global_prev_name.c_str(), "wb");

    int added_prevs = 0;
    find_prevs(sorted_edges.c_str(), m, global_prev, added_prevs);

    fclose(global_prev);
    cerr << "added_prevs " << added_prevs << endl;
    check_file(global_prev_name.c_str(), 2);

    Filename global_prev_all = add_roots(global_prev_name.c_str(), n, added_prevs);
    check_file(global_prev_all.c_str(), 2);

    answer_queries(transformed_inputs.second.c_str(), q, global_prev_all.c_str());
    check_file("output.bin");
    //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;
}