Cycling City

#include <bits/stdc++.h>
using namespace std;
#define PII pair <int, int>
const int MAXN = 200013;
int N, M;
vector <int> edges [MAXN];
vector <int> spanning [MAXN];
int vis [MAXN];
int artic [MAXN];
void mem ()
{
    memset(vis,0,sizeof(vis));
}
void create (int node) // create the spanning tree
{
    vis[node]=1;
    for (int g=0; g<edges[node].size(); g++)
    {
        if (vis[edges[node][g]]) continue;
        spanning[node].push_back(edges[node][g]);
        spanning[edges[node][g]].push_back(node);
        create(edges[node][g]);
    }
}
int timer=1;
int finishing [MAXN];
int find (int node, int prev=0) // find articulation points
{
    vis[node]=1;
    finishing[node]=timer++;
    int mini=finishing[node];
    for (int g=0; g<spanning[node].size(); g++)
    {
        if (vis[spanning[node][g]]) continue;
        int k=find(spanning[node][g], node);
        if (k>=finishing[node]) artic[node]=1;
        if(k<mini)mini=k;
    }
    for (int g=0; g<edges[node].size(); g++)
    {if(edges[node][g]==prev) continue;
        if (finishing[edges[node][g]]<mini) mini=finishing[edges[node][g]];
    }
    return mini;
}
vector <int> artclear, path;
int counter=0;
vector <int> nodes;
int iter [MAXN];
int fromsame [MAXN];
void determinesz (int node) // determine size of biconnected component & search it
{
    nodes.push_back(node); // add node to vector, so we know what nodes are part of biconnected component
    vis[node]=1;
    counter++;
    if (artic[node]) { // if it is a articulation vertex, don't dfs further
        artclear.push_back(node); return; // push it to a special vector
    }
    for (int g=0; g<edges[node].size(); g++)
    {
        if (vis[edges[node][g]]) continue;
        determinesz (edges[node][g]); // dfs if it is not a articulation vertex
    }
}
PII cyc (int node, int iteration, int prev=0) // cycle detection
// note that the iteration counter here is useless; I thought the graph was directed at first :P
{
    iter[node]=iteration; // no use
    vis[node]=1; // just visit the node
    for (int g=0; g<edges[node].size(); g++)
    {if(edges[node][g]==prev || fromsame[node]!=fromsame[edges[node][g]]) continue;
    // if the node is the previous, or they don't belong to the same component, continue
        if (vis[edges[node][g]])
        {
                return PII(edges[node][g], node);  // cycle has been detected!
            continue;
        }
        PII x = cyc (edges[node][g], iteration, node);
        if (x.first!=-1) return x;
    }
    return PII(-1, -1);
}
int d=1;
int findpath (int node1, int node2, int type=1)
{
    vis[node1]=1;
    path.push_back(node1);if(node1==node2)return 1;
    for (int g=0; g<edges[node1].size(); g++)
    {
        if (type && edges[node1][g]==node2) continue;
        if (vis[edges[node1][g]] || fromsame[edges[node1][g]]!=fromsame[node1]) continue;
        int x = findpath(edges[node1][g], node2, 0);
        if (x==1) return 1;
    }
    path.pop_back();
    return 0;
}
int oncyc [MAXN];
vector <int> answer1, answer2, answer3;
int doit (int node, int notequal)
{
    vis[node]=1;
    if (oncyc[node])
    {
        answer1.push_back(node);
        return 1;
    }
    answer1.push_back(node);
    for (int g=0; g<edges[node].size(); g++)
    {
        if (fromsame[edges[node][g]]!=fromsame[node] || vis[edges[node][g]] || edges[node][g]==notequal) continue;
        int t=doit(edges[node][g], notequal);
        if (t) return 1;
    }
    answer1.pop_back(); return 0;
}
void solve (int node)
{
    counter=0;
    determinesz (node);
    if (counter<=2) return;
    for (int t=0; t<nodes.size(); t++) vis[nodes[t]]=0, fromsame[nodes[t]]=d;
    d++;
    int z=1;
    PII r=cyc(nodes[0], 1); // this is for detecting a cycle in the graph; and finding the edge where the problem occurred
        // through some debugging, I've found that somehow no cycle is found in the biconnected component
        // leading me to believe that either the cycle detection is wrong or articulation point detection is wrong
        // or I'm somehow finding biconnected components in a wrong way.
        // However, I haven't been able to find problems with any
    for (int t=0; t<nodes.size(); t++) vis[nodes[t]]=0, iter[nodes[t]]=0;
    findpath(r.first, r.second); // just finds a path between two nodes given edge; but this is not the problem I think
    for (int t=0; t<nodes.size(); t++) vis[nodes[t]]=0;
    if (counter==path.size())
    {
        for (int g=0; g<nodes.size(); g++)
        {
            if (artic[nodes[g]]) continue;
            vis[nodes[g]]=1;
        }
        return;
    }
    for (int t=0; t<path.size(); t++) oncyc[path[t]]=1;
    cout << "YES" << '\n';
    int start=-1, other=-1, end=-1;
    for (int t=0; t<path.size(); t++)
    {
        int nodcyc=path[t];
        for (int y=0; y<edges[nodcyc].size(); y++)
        {
            if (fromsame[edges[nodcyc][y]]!=fromsame[path[t]]) continue;
            if (oncyc[edges[nodcyc][y]]) continue;
            start=path[t], other=edges[nodcyc][y];
        }
        if (start!=-1) break;
    }
    doit(other, start);
    for (int t=0; t<nodes.size(); t++) vis[nodes[t]]=0;
    cout << answer1.size()+1 << ' ' << start << ' ';
    for (int g=0; g<answer1.size(); g++) cout << answer1[g] << ' ';
    cout << '\n';
    end=answer1.back();
    int pos1=-1, pos2=-1;
    for (int t=0; t<path.size(); t++)
    {
        if (path[t]==start) pos1=t;
        if (path[t]==end) pos2=t;
    }
    if (pos2>pos1)
    {
        cout << pos2-pos1+1 << ' ';
        for (int g=pos1; g<=pos2; g++) cout << path[g] << ' '; cout << '\n';
        cout << (pos1+1+(path.size()-pos2)) << ' ';
        for (int g=pos1; g>=0; g--) cout << path[g] << ' ';
        for (int g=path.size()-1; g>=pos2; g--) cout << path[g] << ' '; cout << '\n';
    }
    else
    {
        cout << (path.size()-pos1)+(pos2+1) << ' ';
        for (int g=pos1; g<path.size(); g++) cout << path[g] << ' ';
        for (int g=0; g<=pos2; g++) cout << path[g] << ' '; cout << '\n';
        cout << pos1-pos2+1 << ' ';
        for (int g=pos1; g>=pos2; g--) cout << path[g] << ' ';
        cout << '\n';
    }
    exit(0);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin >> N >> M;
    for (int g=0; g<M; g++)
    {
        int a, b; cin >> a >> b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    for (int g=1; g<=N; g++)
    {
        if (vis[g]) continue;
        create (g);
    }
    mem();
    for (int g=1; g<=N; g++)
    {
        if (vis[g]) continue;
        find(g);
        if (spanning[g].size()>1) artic[g]=1;
        else artic[g]=0;
    }
    mem();
    for (int g=1; g<=N; g++)
    {
        if (vis[g] || artic[g]) continue;
        solve (g);
        for (int t=0; t<artclear.size(); t++) vis[artclear[t]]=0;
        artclear.clear();
        path.clear();
        nodes.clear();
    }
    cout << "NO" << '\n';
    return 0;
}