#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>
#include <time.h>



#define INFILE "maxpath.in"
#define MAX_NODES 100001
#define MAX_PATHS_PER_NODE 522600
#define TOPP 30
#define IDX_LESS_THAN 3
#define TIME_STOP_1 2000 // try 'good' start points
#define TIME_STOP_MS 4150 // @4300 max was 4984ms
#define TEST_MEM 0
#define PROD 0

///////////////////

#ifndef VECTOR_H_
#define VECTOR_H_

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

/* Declare a vector of type `TYPE`. */
#define VECTOR_OF(TYPE) struct { \
    TYPE *data; \
    size_t size; \
    size_t capacity; \
}

/* Initialize `VEC` with `N` capacity. */
#define VECTOR_INIT_CAPACITY(VEC, N) do { \
    (VEC).data = malloc((N) * sizeof(*(VEC).data)); \
    if (!(VEC).data) { \
        fputs("malloc failed!\n", stderr); \
        abort(); \
    } \
    (VEC).size = 0; \
    (VEC).capacity = (N); \
} while (0)

/* Initialize `VEC` with zero elements. */
#define VECTOR_INIT(VEC) VECTOR_INIT_CAPACITY(VEC, 128)

/* Get the amount of elements in `VEC`. */
#define VECTOR_SIZE(VEC) (VEC).size

/* Get the amount of elements that are allocated for `VEC`. */
#define VECTOR_CAPACITY(VEC) (VEC).capacity

/* Test if `VEC` is empty. */
#define VECTOR_EMPTY(VEC) ((VEC).size == 0)

/* Push `VAL` at the back of the vector. This function will reallocate the buffer if
   necessary. */
#define VECTOR_PUSH_BACK(VEC, VAL) do { \
    if ((VEC).size + 1 > (VEC).capacity) { \
        size_t n = (VEC).capacity * 2; \
        void *p = realloc((VEC).data, n * sizeof(*(VEC).data)); \
        if (!p) { \
            fputs("realloc failed!\n", stderr); \
            abort(); \
        } \
        (VEC).data = p; \
        (VEC).capacity = n; \
    } \
    (VEC).data[VECTOR_SIZE(VEC)] = (VAL); \
    (VEC).size += 1; \
} while (0)

/* Get the value of `VEC` at `INDEX`. */
#define VECTOR_AT(VEC, INDEX) (VEC).data[INDEX]

/* Get the value at the front of `VEC`. */
#define VECTOR_FRONT(VEC) (VEC).data[0]

/* Get the value at the back of `VEC`. */
#define VECTOR_BACK(VEC) (VEC).data[VECTOR_SIZE(VEC) - 1]

#define VECTOR_FREE(VEC) do { \
    (VEC).size = 0; \
    (VEC).capacity = 0; \
    free((VEC).data); \
} while(0)

#endif /* !defined VECTOR_H_ */


////////////////////

//int nodes[MAX_NODES][MAX_PATHS_PER_NODE];
#define nodes nodes_work
//int nodes_work[MAX_NODES][MAX_PATHS_PER_NODE];
VECTOR_OF(int) nodes_work[MAX_NODES];
int num_nodes;
int hops, hops_best;
int nodes_last_idx[MAX_NODES];
int nodes_work_last_idx[MAX_NODES];
int nodes_best[MAX_NODES];
unsigned long long score_max=0, score_temp;
int path[MAX_PATHS_PER_NODE], path_best[MAX_PATHS_PER_NODE];
clock_t ts_start;

int read_input() {
    FILE* fp = fopen(INFILE, "r");
    if (fp == NULL)
        return 1;
    int a, b;
    while (!feof(fp)) {
        if (2 == fscanf(fp, "%d %d\n", &a, &b)) {
            if (0 == num_nodes) {
                num_nodes = a;
                continue;
            }

            if (a >= MAX_NODES-1 || b >= MAX_NODES-1) {
                continue; // no mem to store that link
            }
            //printf("link %d <=> %d\n", a, b);
            if (nodes_last_idx[a] >= MAX_PATHS_PER_NODE) {
                    continue; // skip this 1 - already got enough links for this node
            }

            if(VECTOR_EMPTY(nodes[a])) VECTOR_INIT(nodes[a]);
            if(VECTOR_EMPTY(nodes[b])) VECTOR_INIT(nodes[b]);

            VECTOR_PUSH_BACK(nodes[a], b);
            VECTOR_PUSH_BACK(nodes[b], a);

            nodes_last_idx[a]++;
            nodes_last_idx[b]++;
        }
    }

    if (num_nodes > MAX_NODES) num_nodes = MAX_NODES;
    fclose(fp);
    return 0;
}

int cmpfunc (const void * a, const void * b) {
   return ( *(int*)a - *(int*)b );
}

int generate_random_path(int p[MAX_PATHS_PER_NODE], unsigned long long *score, int *hops, int start_point) {
    int more = 99666;
    int i, idx = 0, random_index, random_next_hop;
    int ts_total_ms;
    p[0] = 0;

    while (more > 0 && idx < MAX_PATHS_PER_NODE) {
        if (0 == idx && 0 == p[idx]) { // first - random start point
            if (-1 == start_point) {
                int  top_5p_count = (num_nodes-1) / (100/TOPP);
                if (1 ||  20 > top_5p_count) {
                    p[idx] = rand() % (num_nodes); // totally random
                } else {
                    p[idx] = ((100/TOPP) -1 )*top_5p_count + ( rand() % (top_5p_count) ); // top 10% as start point
                }
            } else {
                p[idx] = start_point;
            }

            more--;
            //continue; // not needed
        }

        ts_total_ms = (clock() / (CLOCKS_PER_SEC / 1000)) - ts_start;
//        printf("%d total ms\n", ts_total_ms);
        if (ts_total_ms  >= TIME_STOP_MS) {
            break;
        }


        if (idx >= MAX_PATHS_PER_NODE-1 || p[idx] >= MAX_NODES-1) {
            break;
        }

        if (0 == nodes_work_last_idx[ p[idx] ]) {
            //printf("dead end -- bye\n");
            break;
        }

        int nz = 0; // valid nodes for this
        int jumps[nodes_work_last_idx[p[idx]]];

#if 0 // populate jumps and hop @ random
        for (i=0; i<nodes_work_last_idx[p[idx]]; i++) {
            int try_node = VECTOR_AT(nodes_work[p[idx]], i);
            if (0 != nodes_work_last_idx[ try_node ] ) {
                //printf("add jump to %d\n", try_node);
                jumps[nz] = VECTOR_AT(nodes_work[p[idx]], i);
                nz++;
            }
        }

        if (0 == nz) {
//            printf("dead end2 (idx=%d) -- bye\n", idx);
            break;
        }

        ts_total_ms = (clock() / (CLOCKS_PER_SEC / 1000)) - ts_start;
        if (ts_total_ms  >= TIME_STOP_MS) {
            break;
        }

        if (idx < IDX_LESS_THAN) {
            qsort(jumps, nz, sizeof(int), cmpfunc);
            int max = 10;
            if (max > nz) max = nz;
            random_index = rand()%max;
            random_next_hop = jumps[random_index];
            //printf("pick good index:%d hop %d, first(%d), last %d   \n", random_index, random_next_hop, jumps[0], jumps[nz-1]);
        } else {
            random_index = rand()%nz;
            random_next_hop = jumps[random_index];
        }

#else
    int max_retry = 1000;
    do {
        random_index = rand() % VECTOR_SIZE(nodes_work[p[idx]]);
        random_next_hop = VECTOR_AT(nodes_work[p[idx]], random_index);
        //printf("gen %d %d\n", random_index, random_next_hop);
        max_retry--;
    } while (max_retry > 0 && 0 == nodes_work_last_idx[ random_next_hop ] );

    if (0 == max_retry || 0 == nodes_work_last_idx[ random_next_hop ]) {
        //printf("dead end3-- bye\n");
        break;
    }
#endif

        nodes_work_last_idx[ p[idx] ] = 0; // this node was visited!
        idx++;
        p[idx] = random_next_hop;

        more--;
    }
    *hops = idx+1;
    return 0;
}

unsigned long long calc_score(int p[MAX_PATHS_PER_NODE],int hops) {
    int i;
    unsigned long long new_score = 0;

    for (i=0; i<(hops); i++) {
        new_score += (i+1) * path[i];
    }
    return new_score;
}

int reverse_path(int p[MAX_PATHS_PER_NODE], unsigned long long *score, int *hops) {
    int i, temp;

    for (i=0; i<(*hops/2); i++) {
        temp = path[i];
        path[i] = path[*hops-i-1];
        path[*hops-i-1] = temp;
    }

    *score = calc_score(p, *hops);
    return 0;
}

void print_path(int p[MAX_PATHS_PER_NODE], int hops, char* header) {
    int i;
    unsigned long long score=0;
    printf("%s ", header);
    for (i=0; i<hops; i++) {
        printf("%d ", path[i]);
        score += (i+1) * path[i];
    }
    printf(" = %lld \n", score);
}

int main() {
    int i = read_input(), total_loops=0, ts_total_ms;
    if (i != 0) {
        printf("err input\n");
        return i;
    }

    ts_start = clock() / (CLOCKS_PER_SEC / 1000);

    struct timeval time;
    gettimeofday(&time,NULL);
    unsigned int seed = (time.tv_usec);
    //seed = 0x5C4754A5;
//    printf("use seed: 0x%X\n", seed);
    srand(seed);
    memset(&path, 0, sizeof(path));

#if TEST_MEM
    unsigned long long memused = /* sizeof (nodes) */ + sizeof(nodes_work);
    memused += sizeof(nodes_last_idx) + sizeof(nodes_work_last_idx) + sizeof(nodes_best);
    memused += sizeof(path) + sizeof(path_best);
    printf("MEMUSED %llu\n", memused/1024/1024);
    return 123;
#endif

#define RETRY_AT ((num_nodes/10)*8)
    // pick 'good' start point:w
    int start_point = num_nodes -1, retries = 3;
    while (1 && start_point >= RETRY_AT) {
        memcpy(nodes_work_last_idx, nodes_last_idx, sizeof(nodes_last_idx));
        score_temp = 0;
        generate_random_path(path, &score_temp, &hops, start_point);
        score_temp = calc_score(path, hops);
        if (score_temp > score_max) {
//            printf("new best score %llu -> %llu (%dh) SP[%d]\n", score_max, score_temp, hops, start_point);
            //memcpy(nodes_best, nodes_work, sizeof(nodes_work));
            memcpy(path_best, path, sizeof(path_best));
            score_max = score_temp;
            hops_best = hops;
        }

        //print_path(path, hops, "FWD ");

        // REVERSE & check score again
//        unsigned long long fwd_score = score_temp;
        reverse_path(path, &score_temp, &hops);
        //print_path(path, hops, "REV ");
        //printf("REVERSE best score(R) %llu -> %llu (%dh)\n", fwd_score, score_temp, hops);

        if (score_temp > score_max) {
//            printf("new REVERSE best score %llu -> %llu (%dh) SP[%d]\n", score_max, score_temp, hops, start_point);
            memcpy(path_best, path, sizeof(path_best));
            score_max = score_temp;
            hops_best = hops;
        }

        total_loops++;

        ts_total_ms = (clock() / (CLOCKS_PER_SEC / 1000)) - ts_start;
        if (ts_total_ms  >= TIME_STOP_1) {
            break;
        }
        start_point--;
        if (start_point < RETRY_AT) {
            retries--;
            start_point = num_nodes - 1;
//            printf("reached %d\n", RETRY_AT);
//            printf("RRR @  %d\n", RETRY_AT);
//            printf(">>>> AGAIN\n");

        }
    }

//    printf("================================================ %dms did %d  loops\n", ts_total_ms, total_loops);
    // random start point
    while (1) {
        memcpy(nodes_work_last_idx, nodes_last_idx, sizeof(nodes_last_idx));
        score_temp = 0;
        generate_random_path(path, &score_temp, &hops, -1);
        score_temp = calc_score(path, hops);
        if (score_temp > score_max) {
            //printf("new best score %llu -> %llu (%dh)\n", score_max, score_temp, hops);
            //memcpy(nodes_best, nodes_work, sizeof(nodes_work));
            memcpy(path_best, path, sizeof(path_best));
            score_max = score_temp;
            hops_best = hops;
        }

        //print_path(path, hops, "FWD ");

        // REVERSE & check score again
//        unsigned long long fwd_score = score_temp;
        reverse_path(path, &score_temp, &hops);
        //print_path(path, hops, "REV ");
        //printf("REVERSE best score(R) %llu -> %llu (%dh)\n", fwd_score, score_temp, hops);

        if (score_temp > score_max) {
            memcpy(path_best, path, sizeof(path_best));
            score_max = score_temp;
            hops_best = hops;
        }

        total_loops++;

        ts_total_ms = (clock() / (CLOCKS_PER_SEC / 1000)) - ts_start;
        if (ts_total_ms  >= TIME_STOP_MS) {
            break;
        }
    }

#if !PROD
    printf("after total of %d loops, best score is %llu with %d hops\n", total_loops, score_max, hops_best);
#endif
    // save score
    FILE *fo = fopen("maxpath.out", "w");
    fprintf(fo, "%u", hops_best);
    for (i=0; i<hops_best; i++) {
        fprintf(fo, "\n%u", path_best[i]);
        //printf("%d ==> %u || %d\n", i, path_best[i], path_best[i]);
    }
    fclose(fo);
    return 0;
}