Flow

bool BFS(const Graph& g, std::map<pair<int, int>, int>& net, int start, int finish, vector<int>& par) {
    vector<bool> vis(g.getSize() + 1, false);
    vector<int> nb;
    std::queue<int> q;
    q.push(start);
    vis[start] = true;
    par[start] = -1;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        nb = g.getNeighbours(v);
        for (auto to : nb) {
            if (!vis[to] && net[make_pair(v, to)] > 0) {
                q.push(to);
                par[to] = v;
                vis[to] = true;
            }
        }
    }
    return vis[finish];
}

void FindDisjointPaths(const Graph& g, int s, int t) {
    std::map<pair<int, int>, int> net;
    vector<vector<int>> ans;
    vector<pair<int, int>> allEdges = g.getAllEdges();
    for (auto edge : allEdges) {
        net[make_pair(edge.first, edge.second)]++;
    }
    vector<int> par(g.getSize() + 1, 0);
    int maxFlow = 0;
    while (BFS(g, net, s, t, par)) {
        int pathFlow = INF;
        vector<int> curPath;
        int v = t;
        while (v != s) {
            int u = par[v];
            pathFlow = std::min(pathFlow, net[make_pair(u, v)]);
            v = u;
        }
        v = t;
        curPath.push_back(t);
        while (v != s) {
            int u = par[v];
            curPath.push_back(u);
            net[make_pair(u, v)] -= pathFlow;
            v = u;
        }
        std::reverse(curPath.begin(), curPath.end());
        for (int i = 0; i < pathFlow; ++i) {
            ans.push_back(curPath);
        }
        maxFlow += pathFlow;
        if (maxFlow >= 2) {
            break;
        }
    }
    if (maxFlow < 2) {
        std::cout << "NO";
    } else {
        std::cout << "YES\n";
        for (int i = 0; i < 2; ++i) {
            for (auto u : ans[i]) {
                std::cout << u << ' ';
            }
            std::cout << std::endl;
        }
    }
}