#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <unordered_map>
#include <cassert>

using namespace std;


class NetworkDevice {
    string label;
    int capacity;
    NetworkDevice* neighbours[256];
public:
    NetworkDevice(string label_, int capacity_);
    bool attachTo(NetworkDevice* device);
    int attachedDevices();
    NetworkDevice* getAttachedDevice(int i);
    bool isAttachedTo(NetworkDevice* device);
    double currentThroughput();

    string getLabel();
    void set_neighbour(NetworkDevice* device);
};

vector<vector<NetworkDevice*>> recursive_helper(NetworkDevice* u, NetworkDevice* v, vector<NetworkDevice*> current_path, vector<vector<NetworkDevice*>> all_paths, unordered_map<string, bool> visited) {
    current_path.push_back(u);
    if (u == v) {
        all_paths.push_back(current_path);
        visited[u->getLabel()] = false;
        return all_paths;
    }
    else {
        for (int i = 0; i < u->attachedDevices(); i++) {
            string name = u->getAttachedDevice(i)->getLabel();
            if (!visited[name]) {
                visited[name] = true;
                recursive_helper(u->getAttachedDevice(i), v, current_path, all_paths, visited);
            }
        }
    }
    /*return all_paths;*/
}

double getThroughput(vector<NetworkDevice*> v) {
    double throughput = 1024;
    for (int i = 0; i < v.size(); i++) {
        if (v[i]->currentThroughput() < throughput) {
            throughput = v[i]->currentThroughput();
        }
    }
    return throughput;
}

vector<string> maxThroughputRoute(NetworkDevice* d1, NetworkDevice* d2) {
    unordered_map<string, bool> visited;
    vector<NetworkDevice*> current_path;
    assert(current_path.size() == 0);
    vector<vector<NetworkDevice*>> paths;
    assert(paths.size() == 0);
    vector<vector<NetworkDevice*>> all_paths = recursive_helper(d1, d2, current_path, paths, visited);
    double maxThroughput = getThroughput(all_paths[0]);
    int max_index = 0;

    for (int i = 1; i < all_paths.size(); i++) {
        if (maxThroughput < getThroughput(all_paths[i])) {
            maxThroughput = getThroughput(all_paths[i]);
            max_index = i;
        }
    }

    vector<string> res;
    current_path = all_paths[max_index];
    for (int i = 0; i < current_path.size(); i++) {
        res.push_back(current_path[i]->getLabel());
    }
    return res;
}

NetworkDevice::NetworkDevice(string label_, int capacity_) {
    label = label_;
    capacity = capacity_;
}

bool NetworkDevice::attachTo(NetworkDevice* device) {
    if (capacity == 256) {
        return false;
    }
    if (isAttachedTo(device)) {
        return false;
    }
    neighbours[capacity] = device;
    capacity++;
    device->set_neighbour(this);
    return true;
}

int NetworkDevice::attachedDevices() {
    return capacity;
}

NetworkDevice* NetworkDevice::getAttachedDevice(int i) {
    if (i < capacity) {
        return neighbours[i];
    }
    return nullptr;
}

bool NetworkDevice::isAttachedTo(NetworkDevice* device) {
    for (int i = 0; i < capacity; i++) {
        if (neighbours[i] == device) {
            return true;
        }
    }
    return false;
}

double NetworkDevice::currentThroughput() {
    if (capacity == 0) {
        return 0;
    }
    return 1024.0 / capacity;
}

string NetworkDevice::getLabel() {
    return label;
}

void NetworkDevice::set_neighbour(NetworkDevice* device) {
    neighbours[capacity] = device;
    capacity++;
}


int main() {

    NetworkDevice* C3 = new NetworkDevice("C3", 2);
    NetworkDevice* C4 = new NetworkDevice("C4", 1);
    NetworkDevice* C5 = new NetworkDevice("C5", 1);
    NetworkDevice* C6 = new NetworkDevice("C6", 1);
    NetworkDevice* C7 = new NetworkDevice("C7", 2);
    NetworkDevice* S0 = new NetworkDevice("S0", 4);
    NetworkDevice* S1 = new NetworkDevice("S1", 4);
    NetworkDevice* S2 = new NetworkDevice("S2", 2);
    NetworkDevice* S8 = new NetworkDevice("S8", 2);
    NetworkDevice* S9 = new NetworkDevice("S9", 3);

    C3->attachTo(S8);
    C3->attachTo(S0);
    S8->attachTo(S9);
    S9->attachTo(C7);
    S9->attachTo(S1);
    C7->attachTo(S2);
    S2->attachTo(S1);
    S1->attachTo(C6);
    S1->attachTo(S0);
    S0->attachTo(C5);
    S0->attachTo(C4);

    vector<string> res = maxThroughputRoute(C3, C7);

    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    cout << endl;

    return 0;
}