// Added some code in 2024 to parse downloaded kml file. See https://www.iwriteiam.nl/D2407.html#1

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <math.h>
#include <cmath> 
#define earthRadiusKm 6371.0

// Code taken from https://stackoverflow.com/questions/10198985/calculating-the-distance-between-2-latitudes-and-longitudes-that-are-saved-in-a

// This function converts decimal degrees to radians
double deg2rad(double deg) {
  return (deg * M_PI / 180);
}

//  This function converts radians to decimal degrees
double rad2deg(double rad) {
  return (rad * 180 / M_PI);
}

/**
 * Returns the distance between two points on the Earth.
 * Direct translation from http://en.wikipedia.org/wiki/Haversine_formula
 * @param lat1d Latitude of the first point in degrees
 * @param lon1d Longitude of the first point in degrees
 * @param lat2d Latitude of the second point in degrees
 * @param lon2d Longitude of the second point in degrees
 * @return The distance between the two points in kilometers
 */
double distanceEarth(double lat1d, double lon1d, double lat2d, double lon2d) {
  double lat1r, lon1r, lat2r, lon2r, u, v;
  lat1r = deg2rad(lat1d);
  lon1r = deg2rad(lon1d);
  lat2r = deg2rad(lat2d);
  lon2r = deg2rad(lon2d);
  u = sin((lat2r - lat1r)/2);
  v = sin((lon2r - lon1r)/2);
  return 2.0 * earthRadiusKm * asin(sqrt(u * u + cos(lat1r) * cos(lat2r) * v * v));
}

char buffer[100001];

bool readLine(FILE *f)
{
    if (!fgets(buffer, 100000, f))
        return false;
        
    int len = strlen(buffer);
    while (len > 0 && (buffer[len-1] == '\r' || buffer[len-1] == '\n'))
    {
        len--;
        buffer[len] = '\0';
    }
    return true;
}

char *copystring(char *str)
{
    char *result = (char*)malloc(strlen(str)+1);
    strcpy(result, str);
    return result;
}

char *substring(char *begin, char *end)
{
    int len = end - begin;
    char *result = (char*)malloc(len+1);
    char *r = result;
    for (char *s = begin; s < end;)
        *r++ = *s++;
    *r = '\0';
    return result;
}

#define NR_POINTS 600

struct EndPoint
{
    char *name;
    char *person;
    double x, y;
    int nr_lines;
    int index;
    EndPoint() : name(0), person(0), nr_lines(0) {}
};
EndPoint points[NR_POINTS];
int nr_points = 0;
int nr_defined_points = 0;

struct Point
{
    double x, y;
    Point *next;
    Point(double _x, double _y) : x(_x), y(_y), next(0) {}
};

struct Line
{
    char *name;
    Point *first_point;
    Point *last_point;
    int i1, i2;
    //double d1, d2;
    double length;
    //bool valid;
    Line() : name(0), first_point(0), last_point(0), length(0) {}
};
Line lines[20000];
int nr_lines;


double dist(Point *p1, Point *p2) { return 1000 * distanceEarth(p1->y, p1->x, p2->y, p2->x); }
double dist(Point *p1, EndPoint &p2) { return 1000 * distanceEarth(p1->y, p1->x, p2.y, p2.x); }

/*
void closestPoint(EndPoint &p, int &p_i, double &p_d)
{
    p_i = -1;
    for (int i = 0; i < nr_points; i++)
    {
        double d = dist(p, points[i]);
        if (p_i == -1 || d < p_d)
        {
            p_i = i;
            p_d = d;
        }
    }
}
*/

void printName(int i)
{
    if (i < 26)
        printf("%c", 'A'+i);
    else if (i < 2*26)
        printf("%c", 'a'+(i-26));
    else
        printf("P%d", i-2*26);
}

char empty_string[1] = { 0 };

bool debug_read = false;

bool parseMUPIkml()
{
    FILE *f = fopen("MUPI.kml", "r");
    if (f == 0)
    {
        printf("Cannot open file 'MUPI.kml'\n");
        return false;
    }
    
    while (readLine(f))
    {
        if (strstr(buffer, "<Placemark>") != 0)
        {
            if (!readLine(f)) return 0;
            char *begin = strstr(buffer, "<name>");
            char *end = strstr(buffer, "</name>");
            char *name = begin != 0 && end != 0 ? substring(begin + 6, end) : empty_string;
            if (debug_read) printf("Placemark |%s|\n", name); 
            
            bool is_point = false;
            bool is_line = 0;
            while (readLine(f) && strstr(buffer, "</Placemark>") == 0)
            {
                if (strstr(buffer, "<Point>") != 0)
                    is_point = true;
                if (strstr(buffer, "<LineString>") != 0)
                    is_line = true;
                char *coord = strstr(buffer, "<coordinates>");
                if (coord != 0)
                {
                    coord += 13;
                    if (is_point)
                    {
                        points[nr_points].index = nr_points;
                        points[nr_points].name = name;
                        points[nr_points].nr_lines = 0;
                        //printf("Point data: |%s|", coord);
                        sscanf(coord, "%lf,%lf", &points[nr_points].x, &points[nr_points].y);
                        //printf(" x = %lf, y = %lf\n", points[nr_points].x, points[nr_points].y);
                        nr_points++;
                    }
                    else if (is_line)
                    {
                        lines[nr_lines].name = name;
                        lines[nr_lines].length = 0;
                        if (!readLine(f)) return 0;
                        char *s = buffer;
                        while (*s == '\t')
                            s++;
                        Point **ref_point = &lines[nr_lines].first_point;
                        while (s != 0 && *s != '\0')
                        {
                            double x, y;
                            sscanf(s, "%lf,%lf", &x, &y);
                            if (debug_read) printf("Point %lf, %lf\n", x, y);
                            lines[nr_lines].last_point = *ref_point = new Point(x, y);
                            ref_point = &(*ref_point)->next;
                            s = strstr(s, " ");
                            if (s != 0)
                                s++;
                        }
                        nr_lines++;
                    }
                }
            }
        }
        //else
        //  printf("%s\n", buffer);
    }

    nr_defined_points = nr_points;
    printf("nr point = %d\n", nr_points);
    printf("nr lines = %d\n", nr_lines);
    
    for (int i = 0; i < nr_lines; i++)
    {
        for (int s = 0; s < 2; s++)
        {
            Point *p = s == 0 ? lines[i].first_point : lines[i].last_point;
            
            bool found = false;
            for (int j = 0; j < nr_points; j++)
                if (dist(p, points[j]) < 1.0)
                {
                    found = true;
                    if (s == 0)
                        lines[i].i1 = j;
                    else
                        lines[i].i2 = j;
                    if (j < nr_defined_points)
                    {
                        p->x = points[j].x;
                        p->y = points[j].y;
                    }
                    else
                    {
                        points[j].x = (points[j].nr_lines * points[j].x + p->x) / (points[j].nr_lines + 1);
                        points[j].y = (points[j].nr_lines * points[j].y + p->y) / (points[j].nr_lines + 1);
                    }
                    points[j].nr_lines++;
                    break;
                }
            if (!found)
            {
                if (nr_points == NR_POINTS)
                {
                    printf("ERROR: Max number points is %d\n", NR_POINTS);
                    return -1;
                }
                points[nr_points].x = p->x;
                points[nr_points].y = p->y;
                points[nr_points].nr_lines = 1;
                if (s == 0)
                    lines[i].i1 = nr_points;
                else
                    lines[i].i2 = nr_points;
                nr_points++;
            }
        }
    }
    
    for (int i = 0; i < nr_lines; i++)
    {
        lines[i].first_point->x = points[lines[i].i1].x;
        lines[i].first_point->y = points[lines[i].i1].y;
        lines[i].last_point->x = points[lines[i].i2].x;
        lines[i].last_point->y = points[lines[i].i2].y;
        
        // Calculate distance
        for (Point *p = lines[i].first_point; p != 0 && p->next != 0; p = p->next)
            lines[i].length += dist(p, p->next);
    }
    printf("nr point = %d\n", nr_points);

    f = 0;
    for (int i = 0; i < nr_points; i++)
    {
        int nr_in = 0;
        int nr_out = 0;
        for (int j = 0; j < nr_lines; j++)
        {
            if (lines[j].i1 == i)
                nr_out++;
            if (lines[j].i2 == i)
                nr_in++;
        }
        if (nr_in == 0 || nr_out == 0)
        {
            printf("INOUT %3d: %2d %2d", i, nr_in, nr_out);
            if (points[i].name != 0)
                printf(" %s", points[i].name);
            printf("\n");
            if (f == 0)
            {
                f = fopen("MUPIerrors.kml", "w");
                fprintf(f, "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
                fprintf(f, "<kml xmlns=\"http://www.opengis.net/kml/2.2\" xmlns:gx=\"http://www.google.com/kml/ext/2.2\" xmlns:kml=\"http://www.opengis.net/kml/2.2\" xmlns:atom=\"http://www.w3.org/2005/Atom\">\n");
                fprintf(f, "<Document>\n");
            }
            fprintf(f, "<Placemark><name>INOUT %3d: %2d %2d</name>\n", i, nr_in, nr_out);
            fprintf(f, "<Point><coordinates>%lf,%lf,0</coordinates></Point></Placemark>\n", points[i].x, points[i].y);
        }
    }
    if (f != 0)
    {
        fprintf(f, "</Document>\n</kml>\n");
        fclose(f);
        f = 0;
        return false; // There were errors
    }
    
    return true;
}

double ppdistance[NR_POINTS][NR_POINTS];
double ppto[NR_POINTS][NR_POINTS];
#define MAX_DIST 1000000.0

void calcDistnaceMatrix()
{   
    for (int i = 0; i < nr_points; i++)
        for (int j = 0; j < nr_points; j++)
        {
            ppdistance[i][j] = MAX_DIST;
            ppto[i][j] = j;
        }
    for (int i = 0; i < nr_points; i++)
        ppdistance[i][i] = 0;
            
    for (int i = 0; i < nr_lines; i++)
        ppdistance[lines[i].i1][lines[i].i2] = lines[i].length;
        
    // Floyds:
    for (int j = 0; j < nr_points; j++)
        for (int i = 0; i < nr_points; i++)
            for (int k = 0; k < nr_points; k++)
            {
                double d = ppdistance[i][j] + ppdistance[j][k];
                if (d < ppdistance[i][k])
                {
                    ppdistance[i][k] = d;
                    ppto[i][k] = ppto[i][j];
                }
            }
}

void printMatrix()
{   
    printf("\n     ");
    for (int i = 0; i < nr_defined_points; i++)
        printf(" %5d", i);
    printf("\n");
    for (int j = 0; j < nr_defined_points; j++)
    {
        printf("%3d :", j);
        for (int i = 0; i < nr_defined_points; i++)
        {
            int equal = -1;
            for (int k = 0; k < nr_defined_points; k++)
                if (i != j && k != i && k != j && ppdistance[j][k] + ppdistance[k][i] == ppdistance[j][i])
                {
                    equal = k;
                    break;
                }
            if (equal > -1)
                printf("  (%2d)", equal);
            else
                printf(" %5d", (int)round(ppdistance[j][i]));
        }
        printf("\n");
    }
}

bool readPersonInfo(const char *fn)
{
    FILE *f = fopen(fn, "r");
    if (f == 0)
    {
        printf("Error: Cannot open '%s'\n", fn);
        return false;
    }

    // Code added in 2024   
    if (strstr(fn, ".kml") != 0)
    {
        bool no_errors = true;
        while (readLine(f))
        {
            if (strstr(buffer, "<Placemark>") != 0)
            {
                if (!readLine(f)) return 0;
                char *begin = strstr(buffer, "<name>");
                char *end = strstr(buffer, "</name>");
                if (end == 0) end = buffer + strlen(buffer);
                char *name = begin != 0 ? substring(begin + 6, end) : empty_string;
                bool is_aki = strncmp(name, "AKI", 3) == 0;
                if (debug_read) printf("Placemark |%s|\n", name); 
                
                bool is_point = false;
                while (readLine(f) && strstr(buffer, "</Placemark>") == 0)
                {
                    if (strstr(buffer, "<Point>") != 0)
                        is_point = true;
                    char *coord = strstr(buffer, "<coordinates>");
                    if (coord != 0 && is_point && !is_aki)
                    {
                        coord += 13;
                        if (*coord == '\0' && readLine(f))
                        {
                            coord = buffer;
                            while (*coord == ' ')
                                coord++;
                        }
                        double x, y;
                        sscanf(coord, "%lf,%lf", &x, &y);
                        Point point(x, y);
                        EndPoint *min_end_point = 0;
                        double min_dist;
                        for (int i = 0; i < nr_points; i++)
                            if (points[i].name != 0)
                            {
                                double d = dist(&point, points[i]);
                                if (i == 0 || d < min_dist)
                                {
                                    min_end_point = points + i;
                                    min_dist = d;
                                }
                            }
                        if (min_dist > 15.0)
                        {
                            printf("Error: No end-point close to %lf, %lf (%lf) for %s\n", x, y, min_dist, name);
                            no_errors = false;
                        }
                        else if (min_end_point->person != 0)
                        {
                            printf("Error: End-point already in used for %s, cannot assign %s at %lf, %lf",
                                min_end_point->person, name, x, y);
                            no_errors = false;
                        }
                        else
                        {
                            min_end_point->person = copystring(name);
                        }
                    }
                }
            }
        }
        return no_errors;   
    }
    
    while (readLine(f))
    {
        char *s = buffer;
        while (*s != '\0' && *s != ' ' && *s != ':')
            s++;
        *s++ = '\0';
        while (*s == ' ' || *s == ':')
            s++;
        bool found = false;
        for (int i = 0; i < nr_defined_points; i++)
            if (strcmp(points[i].name, buffer) == 0)
            {
                found = true;
                if (points[i].person != 0)
                    printf("Error: Person for '%s' already set to '%s'\n", points[i].name, points[i].person);
                else
                    points[i].person = copystring(s);
            }
        if (!found)
            printf("Error: No '%s'\n", buffer);
    }
    
    fclose(f);
    
    return true;
}

#define N 63
#define MAX 100000

long mat[N][N];
long add_mat = 0;

EndPoint *places[N];
int n = 0;


struct Edge
{
    int place;
    int distance;
};

struct Place
{
    Edge edges[N-1];
};

Place out_places[N];
Place in_places[N];

void print_mat(FILE *f)
{
    for (int i = 0; i < n; i++)
        fprintf(f, " %5s", places[i]->name);
    fprintf(f, "\n");
    for (int i = 0; i < n; i++)
    {
        fprintf(f, "%5s ", places[i]->name);
        for (int j = 0; j < n; j++)
            if (i == j)
                fprintf(f, "      ");
            else
                fprintf(f, " %5ld", mat[i][j]);
        fprintf(f, "\n");
    }
    fprintf(f, "\n");
}

void init(FILE *f)
{
    int place_index[N];
    for (int i = 0; i < nr_defined_points; i++)
        if (points[i].person != 0)
            places[n++] = &points[i];
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            mat[i][j] = round(ppdistance[places[i]->index][places[j]->index]);
    
    fprintf(f, "Distances according to selected places\n");
    print_mat(f);
            
    // Hungarian reduction
    for (int i = 0; i < n; i++)
    {
        int min_v = MAX;
        for (int j = 0; j < n; j++)
            if (i != j && mat[j][i] < min_v)
                min_v = mat[j][i];
        add_mat += min_v;
        for (int j = 0; j < n; j++)
            if (i != j)
                mat[j][i] -= min_v;
    }
    for (int i = 0; i < n; i++)
    {
        int min_v = MAX;
        for (int j = 0; j < n; j++)
            if (i != j && mat[i][j] < min_v)
                min_v = mat[i][j];
        add_mat += min_v;
        for (int j = 0; j < n; j++)
            if (i != j)
                mat[i][j] -= min_v;
    }
    
    fprintf(f, "After hungarian reduction (total %ld)\n", add_mat);
    print_mat(f);

    for (int i = 0; i < n; i++)
    {
        int ps = 0;
        for (int j = 0; j < n; j++)
            if (i != j)
            {
                long pd = mat[i][j];
                int pi = j;
                for (int k = 0; k < ps; k++)
                    if (out_places[i].edges[k].distance > pd)
                    {
                        int h_pd = out_places[i].edges[k].distance;
                        int h_pi = out_places[i].edges[k].place;
                        out_places[i].edges[k].distance = pd;
                        out_places[i].edges[k].place = pi;
                        pd = h_pd;
                        pi = h_pi;
                    }
                out_places[i].edges[ps].distance = pd;
                out_places[i].edges[ps].place = pi;
                
                pd = mat[j][i];
                pi = j;
                for (int k = 0; k < ps; k++)
                    if (in_places[i].edges[k].distance > pd)
                    {
                        int h_pd = in_places[i].edges[k].distance;
                        int h_pi = in_places[i].edges[k].place;
                        in_places[i].edges[k].distance = pd;
                        in_places[i].edges[k].place = pi;
                        pd = h_pd;
                        pi = h_pi;
                    }
                in_places[i].edges[ps].distance = pd;
                in_places[i].edges[ps].place = pi;
                ps++;
            }
    }
}


struct Sol
{
    long d;
    long sel_d;
    int edges[2];
    struct
    {
        int degree;
        int p[2];
    } ps[N];
    Sol *next;

    void init(int p1, int p2)
    {
        for (int i = 0; i < n; i++)
        {
            ps[i].degree = 0;
            ps[i].p[0] = -1;
            ps[i].p[1] = -1;
        }
        sel_d = 0;
        add_edge(p1, p2);
        edges[0] = p1;
        edges[1] = p2;
        calc();
    }
    
    void add_edge(int p1, int p2)
    {
        ps[p1].degree++;
        ps[p1].p[1] = p2;
        ps[p2].degree++;
        ps[p2].p[0] = p1;
        sel_d += mat[p1][p2];
    }
    
    void add(int p1, int p2)
    {
        add_edge(p1, p2);
        if (p2 == edges[0])
            edges[0] = p1;
        else if (p1 == edges[1])
            edges[1] = p2;
        calc();
    }
    
    void calc()
    {
        d = 2 * sel_d;
        for (int i = 0; i < n; i++)
        {
            Edge *out[2];
            int nr_out = 0;
            if (ps[i].p[1] == -1)
            {
                for (int j = 0; j < n-1 && nr_out < 2; j++)
                    if (ps[out_places[i].edges[j].place].p[0] == -1)
                        out[nr_out++] = &out_places[i].edges[j];
                if (nr_out == 1)
                    out[1] = out[0];
            }
                
            Edge *in[2];
            int nr_in = 0;
            if (ps[i].p[0] == -1)
            {
                for (int j = 0; j < n-1 && nr_in < 2; j++)
                    if (ps[in_places[i].edges[j].place].p[1] == -1)
                        in[nr_in++] = &in_places[i].edges[j];
                if (nr_in == 1)
                    in[1] = in[0];
            }
            
            if (nr_in != 0 && nr_out != 0)
            {
                if (out[0]->place == in[0]->place || (out[0]->place == edges[0] && in[0]->place == edges[1]))
                {
                    int d1 = out[0]->distance + in[1]->distance;
                    int d2 = out[1]->distance + in[0]->distance;
                    d += d1 < d2 ? d1 : d2;
                }
                else
                    d += out[0]->distance + in[0]->distance;
            }
            else if (nr_out != 0)
                d += out[0]->distance;
            else if (nr_in != 0)
                d += in[0]->distance;
        }
    }
            
    bool equal(Sol *sol)
    {
        if (   sol->d != d
            || sol->sel_d != sel_d
            || sol->edges[0] != edges[0]
            || sol->edges[1] != edges[1])
            return false;
        for (int i = 0; i < n; i++)
            if (sol->ps[i].p[0] != ps[i].p[0] || sol->ps[i].p[1] != ps[i].p[1])
                return false;
        return true;
    }
    void print()
    {
        int p = edges[0];
        int p_p = -1;
        while (p != edges[1])
        {
            if (p < 0 || p >= n)
            {
                printf("%d!!!\n", p);
                return;
            }
            printf("%s-", places[p]->name);
            int n_p = -1;
            for (int i = 0; i < ps[p].degree; i++)
                if (ps[p].p[i] != p_p)
                {
                    n_p = ps[p].p[i];
                    break;
                }
            p_p = p;
            p = n_p;
        }
        printf("%s = %ld (%ld)\n", places[p]->name, d, sel_d);
    }
    
    void close()
    {
        int m = -1;
        for (int i = 0; i < n; i++)
            if (ps[i].degree == 0)
            {
                m = i;
                break;
            }
        if (m == -1 || ps[edges[0]].degree != 1 || ps[edges[1]].degree != 1)
        {
            printf("Error %d %d %d\n", m, ps[edges[0]].degree, ps[edges[1]].degree);
            return;
        }
        add_edge(edges[1], m);
        add_edge(m, edges[0]);
        edges[0] = 0;
        edges[1] = 0;
        d = 2 * sel_d;
    }
    void print_comp()
    {
        printf("%s", places[0]->name);
        //int p_p = 0;
        int p = ps[0].p[1];
        for (int i = 0; i <= n; i++)
        {
            printf("-%s", places[p]->name);
            if (p == 0)
                break;
            p = ps[p].p[1];
        }
        printf(" = %ld\n", sel_d + add_mat);
    }
    void get_indexes(int *indexes)
    {
        indexes[0] = places[0]->index;
        int p_p = 0;
        int p = ps[0].p[1];
        for (int i = 1; i < n; i++)
        {
            indexes[i] = places[p]->index;
            if (p == 0)
                break;
            p = ps[p].p[1];
        }
    }
};

Sol *old_sols = 0;
Sol *new_sol(Sol &sol, Sol *next)
{
    Sol *n_sol;
    if (old_sols != 0)
    {
        n_sol = old_sols;
        old_sols = old_sols->next;
    }
    else
        n_sol = new Sol;
    *n_sol = sol;
    n_sol->next = next;
    return n_sol;
}

void free_sols(Sol *sols)
{
    if (sols == 0) return;
    Sol **ref_sols = &sols;
    while (*ref_sols != 0)
        ref_sols = &(*ref_sols)->next;
    *ref_sols = old_sols;
    old_sols = sols;
}

#define MAX_PSOL 10000

void insert(Sol &sol, Sol **ref_sol)
{
    int n = 0;
    
    for (;; n++)
        if (*ref_sol == 0 || (*ref_sol)->d > sol.d)
        {
            (*ref_sol) = new_sol(sol, (*ref_sol));
            break;
        }
        else if (sol.equal(*ref_sol))
            return;
        else
            ref_sol = &(*ref_sol)->next;
    for (;n < MAX_PSOL; n++)
        if (*ref_sol == 0)
            return;
        else
            ref_sol = &(*ref_sol)->next;
    if (*ref_sol != 0)
    {
        free_sols(*ref_sol);
        *ref_sol = 0;
    }
}

void solve2(int *indexes)
{
    init(stdout);
    
    Sol *cur_sols = 0;
    for (int i = 0; i < n-1; i++)
        for (int j = i+1; j < n; j++)
            if (mat[i][j] == 0)
            {
                Sol sol;
                sol.init(i, j);
                insert(sol, &cur_sols);
            }
        
    for (int pass = 0; pass < n-3; pass++)
    {
        fprintf(stderr, "pass %d\n", pass);
        Sol *next_sols = 0;
        for (Sol *sol = cur_sols; sol != 0; sol = sol->next)
        {
            for (int i = 0; i < 2; i++)
            {
                int p = sol->edges[1];
                for (int k = 0; k < n-1; k++)
                {
                    int p2 = out_places[p].edges[k].place;
                    if (sol->ps[p2].degree == 0)
                    {
                        Sol n_sol = *sol;
                        n_sol.add(p, p2);
                        insert(n_sol, &next_sols);
                    }
                }
                p = sol->edges[0];
                for (int k = 0; k < n-1; k++)
                {
                    int p2 = in_places[p].edges[k].place;
                    if (sol->ps[p2].degree == 0)
                    {
                        Sol n_sol = *sol;
                        n_sol.add(p2, p);
                        insert(n_sol, &next_sols);
                    }
                }
            }
        }
        Sol *prev_sols = cur_sols;
        cur_sols = next_sols;
        free_sols(prev_sols);
    }
    printf("\n\n");
    
    Sol *final_sols = 0;
    for (Sol *sol = cur_sols; sol != 0; sol = sol->next)
    {
        Sol f_sol = *sol;
        f_sol.close();
        //if (f_sol.d <= 2*d_min)
            insert(f_sol, &final_sols);
    }
    for (Sol *sol = final_sols; sol != 0; sol = sol->next)
        sol->print_comp();
    final_sols->get_indexes(indexes);
}

void create_KML_sol(int *sol_indexes)
{
        
    FILE *f = fopen("MUPIroute.kml", "w");
    if (f == 0)
    {
        printf("Error: Cannot open 'MUPIroute.kml' for writing\n");
        return;
    }
    fprintf(f, "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
    fprintf(f, "<kml xmlns=\"http://www.opengis.net/kml/2.2\" xmlns:gx=\"http://www.google.com/kml/ext/2.2\" xmlns:kml=\"http://www.opengis.net/kml/2.2\" xmlns:atom=\"http://www.w3.org/2005/Atom\">\n");
    fprintf(f, "<Document>\n");
    fprintf(f, "<Style id=\"redline\"><LineStyle><color>ff0000ff</color><width>4</width></LineStyle></Style>\n");

    for (int i = 0; i < n; i++)
    {
        EndPoint &point = points[sol_indexes[i]];
        fprintf(f, "<Placemark><name>%s</name>\n", point.person);
        fprintf(f, "<Point><coordinates>%lf,%lf,0</coordinates></Point></Placemark>\n", point.x, point.y);
    }
    
    for (int i = 0; i < n; i++)
    {
        int from = sol_indexes[i];
        int to = sol_indexes[(i+1)%n];
        EndPoint &point = points[from];
        fprintf(f, "<Placemark><name>Route %d</name><styleUrl>redline</styleUrl><LineString><tessellate>1</tessellate><coordinates>\n%lf,%lf,0", i+1, point.x, point.y);
        while (from != to)
        {
            int next_to = ppto[from][to];
            for (int j = 0; j < nr_lines; j++)
                if (lines[j].i1 == from && lines[j].i2 == next_to)
                {
                    for (Point* point = lines[j].first_point->next; point != 0; point = point->next)
                        fprintf(f, " %lf,%lf,0", point->x, point->y);
                    break;
                }
            from = next_to;
        }
        fprintf(f, "</coordinates>\n</LineString>\n</Placemark>\n");
    }
    fprintf(f, "</Document>\n</kml>\n");
    fclose(f);
}

int main(int argc, char *argv[])
{
    if (!parseMUPIkml())
        return -1;
        
    calcDistnaceMatrix();

    if (argc != 2)
    {
        printMatrix();
        return 0;
    }
    
    if (!readPersonInfo(argv[1]))
        return -1;
    
    printf("solve2\n");
    
    int sol_indexes[N]; 
    solve2(sol_indexes);
    
    create_KML_sol(sol_indexes);

    return 0;
}