#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

vector<int> bfs(vector<int> someGraph[], int source, int destination) {
    int prev[1000] = {0};
    bool visited[1000] = {false};
    prev[source] = 0;                                                      )
    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;
    for (int i = destination; i != source; i = prev[i]) {
        path.push_back(i);
    }
    path.push_back(source);

    return path;
}

void printPath(vector<int> path) {
    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];

    while (fin >> n1) {
        fin >> n2;
        graph[n1].push_back(n2);
        graph[n2].push_back(n1);
        edges++;
    }
    cout << edges << "\n";

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

    for (int i = 0; i < 1000; i++) {
        if (graph[i].empty()) {
            isolates[numOfIsolates++] = i;
        }
    }

    cout << numOfIsolates << "\n";

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

    for (int i = 0; i < 1000; i++) {
        if (graph[i].size() > max) {
            maxNode = i;
            max = graph[i].size();
        }
    }
    cout << "\n";
    cout << maxNode << " " << max << "\n";

    vector<int> maxDist;

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