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

typedef struct City {
    int index;
    struct City** connections;
    int connectionCount;
    int presage;
} City;

typedef struct Program {
    char* resource;
    FILE* writer;
    City** cityList;
    int cityCount;
} Program;

Program* createProgram(char* resource) {
    Program* program = (Program*)malloc(sizeof(Program));
    program->resource = resource;
    program->writer = fopen("./taxi.out", "w");
    program->cityList = (City**)malloc(sizeof(City*) * 100);
    program->cityCount = 0;
    return program;
}

int findWay(City* thisCity, City** visitCity, int visitCityCount, int price) {
    for (int i = 0; i < thisCity->connectionCount; i++) {
        City* city = thisCity->connections[i];
        int contains = 0;
        for (int j = 0; j < visitCityCount; j++) {
            if (visitCity[j] == city) {
                contains = 1;
                break;
            }
        }
        if (!contains) {
            for (int j = 0; j < thisCity->connectionCount; j++) {
                City* c = thisCity->connections[j];
                if (!visitCity[j]) {
                    visitCity[visitCityCount++] = thisCity;
                    visitCity[visitCityCount++] = thisCity;
                    return findWay(c, visitCity, visitCityCount, price + (thisCity->presage - c->presage) * (thisCity->presage - c->presage));
                }
            }
        }
        if (contains) continue;
        visitCity[visitCityCount++] = thisCity;
        visitCity[visitCityCount++] = thisCity;
        return findWay(city, visitCity, visitCityCount, price + (thisCity->presage - city->presage) * (thisCity->presage - city->presage));
    }
    visitCity[visitCityCount++] = thisCity;
    visitCity[visitCityCount++] = thisCity;
    return price;
}

void loadContent(Program* program) {
    char* content;
    FILE* file = fopen(program->resource, "r");
    fseek(file, 0, SEEK_END);
    long fileSize = ftell(file);
    rewind(file);
    content = (char*)malloc(sizeof(char) * fileSize);
    fread(content, 1, fileSize, file);
    fclose(file);
    if (content == NULL) return;
    char* line = strtok(content, "\n");
    int cityCount = atoi(strtok(line, " "));
    int highWayCount = atoi(strtok(NULL, " "));
    line = strtok(NULL, "\n");
    char* cities = strtok(line, " ");
    for (int i = 0; i < cityCount; i++) {
        int index = atoi(strtok(cities, " "));
        City* city = (City*)malloc(sizeof(City));
        city->index = index;
        city->connections = (City**)malloc(sizeof(City*) * 100);
        city->connectionCount = 0;
        city->presage = rand() % 9 + 1;
        program->cityList[i] = city;
        cities = strtok(NULL, " ");
    }
    for (int i = 0; i < highWayCount; i++) {
        line = strtok(NULL, "\n");
        int firstCityIndex = atoi(strtok(line, " "));
        int secondCityIndex = atoi(strtok(NULL, " "));
        City* firstCity = NULL;
        City* secondCity = NULL;
        for (int j = 0; j < cityCount; j++) {
            if (program->cityList[j]->index == firstCityIndex) {
                firstCity = program->cityList[j];
            }
            if (program->cityList[j]->index == secondCityIndex) {
                secondCity = program->cityList[j];
            }
        }
        if (firstCity == NULL || secondCity == NULL) continue;
        firstCity->connections[firstCity->connectionCount++] = secondCity;
        secondCity->connections[secondCity->connectionCount++] = firstCity;
    }
    for (int i = 0; i < cityCount; i++) {
        fprintf(program->writer, "%d ", program->cityList[i]->presage);
    }
    fprintf(program->writer, "\n");
    free(content);
}

void write(Program* program, char* word) {
    fprintf(program->writer, "%s", word);
}

void writeClose(Program* program) {
    fclose(program->writer);
}

void start(Program* program) {
    loadContent(program);
    int _days = 0;
    int _price = 0;
    City** _visitCity = (City**)malloc(sizeof(City*) * 100);
    int _visitCityCount = 0;
    for (int i = 0; i < program->cityCount; i++) {
        int days = 0;
        int price = 0;
        City** visitCity = (City**)malloc(sizeof(City*) * 100);
        int visitCityCount = 0;
        int freeCity = 0;
        for (int j = 0; j < program->cityCount; j++) {
            if (!visitCity[j]) freeCity++;
        }
        while (freeCity != 0 || visitCityCount == 0) {
            City* startCity = visitCityCount == 0 ? program->cityList[i] : visitCity[visitCityCount - 1];
            price += findWay(startCity, visitCity, visitCityCount, price);
            freeCity = 0;
            for (int j = 0; j < program->cityCount; j++) {
                if (!visitCity[j]) freeCity++;
            }
            days++;
        }
        if (price < _price || price != 0) {
            _days = days;
            _price = price;
            _visitCity = visitCity;
            _visitCityCount = visitCityCount;
        }
    }
    fprintf(program->writer, "%d\n", _days);
    for (int i = 0; i < _visitCityCount; i++) {
        fprintf(program->writer, "%d ", _visitCity[i]->index);
        if (i + 1 != _visitCityCount) {
            if (_visitCity[i]->index == _visitCity[i + 1]->index) {
                fprintf(program->writer, "\n");
            }
        }
    }
    free(_visitCity);
    writeClose(program);
}

int main() {
    Program* program = createProgram("./taxi.00.in");
    start(program);
    free(program);
    return 0;
}