#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

vector<int> bfs(vector<int> someGraph[], int source, int destination) {     //This function will return a vector, this vector is going to keep the path from source to destination
    int prev[1000] = {0};                                                   //Keeps the previous node of the index
    bool visited[1000] = {false};                                           //Keeps track if whether a node was visited during BFS
    prev[source] = 0;                                                       //The parent(root)
    queue<int> q;
    q.push(source);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int j = 0; j < someGraph[cur].size(); j++) {
            if (!visited[someGraph[cur][j]]) {
                visited[someGraph[cur][j]] = true;
                prev[someGraph[cur][j]] = cur;
                q.push(someGraph[cur][j]);
            }
        }
    }
    vector<int> path;                                                       //Vector to keep our shortest path
    for (int i = destination; i != source; i = prev[i]) {                   //We trace back
        path.push_back(i);
    }
    path.push_back(source);

    return path;
}

void printPath(vector<int> path) {                                          //Printing the vector from the back, because when we found the path it was backwards
    for (int i = path.size() - 1; i >=0; i--) {
        cout << path[i] << " ";
    }
    cout << "\n";
}

int main() {
    ifstream fin("graphedges14.txt");
    int n1, n2;
    int edges = 0;
    vector<int> graph[1000];                            //Declare the array of vectors of integer type (adjacency list)

    while (fin >> n1) {                                 //Read first node
        fin >> n2;                                      //Read second node
        graph[n1].push_back(n2);                        //In n1 we put n2
        graph[n2].push_back(n1);                        //In n2 we put n1 (vice versa because it is indirected)
        edges++;
    }
    cout << edges << "\n";

    int isolates[1000];
    int numOfIsolates = 0;
    int max = 0;
    int maxNode;

    for (int i = 0; i < 1000; i++) {                    //For loop to find the isolates
        if (graph[i].empty()) {                         //If the vector is empty it's an isolate
            isolates[numOfIsolates++] = i;              //A counter for our isolates in an array form, the last number in the array is the number of isolates
        }
    }

    cout << numOfIsolates << "\n";

    for (int i = 0; i < numOfIsolates; i++) {
        cout << isolates[i] << " ";
    }

    for (int i = 0; i < 1000; i++) {                    //For loop to calculate the max node(which is the node with maximum connections)
        if (graph[i].size() > max) {                    //If the number of edges of the node is bigger than the max, then the max node is going to be equal of this node, and max is going to be the number of edges of this node
            maxNode = i;                                //Size function returns how many elements in the vector
            max = graph[i].size();
        }
    }
    cout << "\n";
    cout << maxNode << " " << max << "\n";

    vector<int> maxDist;                                //The diameter

    for (int i = 0; i < 1000; i++) {
        for (int j = 0; j < 1000; j++) {
            if(!graph[i].empty() && !graph[j].empty()) {
                vector<int> dist = bfs(graph, i, j);    //Use the BFS function to find the longest shortest path
                if (dist > maxDist) {
                    maxDist = dist;
                }
            }
        }
    }

    printPath(maxDist);

    int a = 363; int b = 642;
    int c = 738; int d = 685;
    int e = 739; int f = 891;
    vector<int> path = bfs(graph, a, b);
    printPath(path);
    path.clear();
    path = bfs(graph, c, d);
    printPath(path);
    path.clear();
    path = bfs(graph, e, f);
    printPath(path);

    vector<int> newGraph[1000];
    fin.clear();
    fin.seekg(0);
    edges = 0;
    while (fin >> n1) {
        if (n1 % 17 == 0 || n1 == 224 || n1 == 611 || n1 == 424 || n1 == 982 || n1 == 61) {
            fin >> n2;
            continue;
        }
        fin >> n2;
        if(n2 % 17 == 0 || n2 == 224 || n2 == 611 || n2 == 424 || n2 == 982 || n2 == 61)
            continue;

        newGraph[n1].push_back(n2);
        newGraph[n2].push_back(n1);
        edges++;
    }

    cout << "\n" << edges << "\n";
    numOfIsolates = 0;
    for (int i = 0; i < 1000; i++) {
        if (newGraph[i].empty()) {
            if (!(i % 17 == 0 || i == 224 || i == 611 || i == 424 || i == 982 || i == 61)) {
                isolates[numOfIsolates++] = i;
            }
        }
    }
    cout << numOfIsolates << "\n";
    for (int i = 0; i < numOfIsolates; i++) {
        cout << isolates[i] << " ";
    }
    max = 0;
    for (int i = 0; i < 1000; i++) {
        if (newGraph[i].size() > max) {
            maxNode = i;
            max = newGraph[i].size();
        }
    }
    cout << "\n";
    cout << maxNode << " " << max << "\n";


        for (int i = 0; i < 1000; i++) {
        for (int j = 0; j < 1000; j++) {
            if(!graph[i].empty() && !graph[j].empty() && i % 17 !=0 && j % 17 !=0) {
                vector<int> dist = bfs(graph, i, j);    //Use the BFS function to find the longest shortest path
                if (dist > maxDist) {
                    maxDist = dist;
                }
            }
        }
    }

    printPath(maxDist);

    path = bfs(newGraph, a, b);
    printPath(path);
    path.clear();
    path = bfs(newGraph, c, d);
    printPath(path);
    path.clear();
    path = bfs(newGraph, e, f);
    printPath(path);

    return 0;
}