d533b362.cpp

#include <bits/stdc++.h>
#define alive std::cout << "$LINE @" << __LINE__ << " ALIVE" << std::endl
#define watch(var) std::cout << "$ LINE @" << __LINE__ << " FUN @" << __FUNCTION__ \
                             << " VAR @" << (#var) << ": " << (var) << std::endl

using namespace std;

typedef int i32;
typedef unsigned int u32;
typedef long long i64;
typedef unsigned long long u64;
typedef double f64;
typedef long double f128;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    x = 0;
    bool neg = false;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

template <typename Tp>
inline Tp gcd(Tp n, Tp m)
{
    while (m)
    {
        Tp t = n % m;
        n = m;
        m = t;
    }
    return n;
}

const int N = 2000 + 5;

int n, m;

int head[N], E = 1;
struct Edge
{
    int to, next;
    bool open;
} e[N * 2];
inline void addEdge(const int &u, const int &v)
{
    e[++E] = (Edge){v, head[u], true};
    head[u] = E;
}
inline void addE(const int &u, const int &v)
{
    addEdge(u, v);
    addEdge(v, u);
}

pii edge[N];

int dfn[N], low[N], tim = 0;

inline void clear()
{
    memset(dfn + 1, 0, sizeof(int) * n);
    memset(low + 1, 0, sizeof(int) * n);
    tim = 0;
}

bool bridge[N];

void tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++tim;
    for (int i = head[u], v; v = e[i].to, i; i = e[i].next)
    {
        if (v != fa && e[i].open)
        {
            if (!dfn[v])
            {
                tarjan(v, u);
                low[u] = std::min(low[u], low[v]);
                if (low[v] > dfn[u])
                {
                    bridge[i >> 1] = true;
                }
            }
            else
            {
                low[u] = std::min(low[u], dfn[v]);
            }
        }
    }
}

void tarjan(int u, int fa, int &ans)
{
    dfn[u] = low[u] = ++tim;
    for (int i = head[u], v; v = e[i].to, i; i = e[i].next)
    {
        if (v != fa && e[i].open)
        {
            if (!dfn[v])
            {
                tarjan(v, u, ans);
                low[u] = std::min(low[u], low[v]);
                if (low[v] > dfn[u] && !bridge[i >> 1])
                {
                    ++ans;
                }
            }
            else
            {
                low[u] = std::min(low[u], dfn[v]);
            }
        }
    }
}

int main()
{
    read(n), read(m);
    for (int i = 1; i <= m; ++i)
    {
        int &u = edge[i].first, &v = edge[i].second;
        read(u), read(v);
        addE(u, v);
    }

    for (int i = 1; i <= n; ++i)
    {
        if (!dfn[i])
        {
            tarjan(i, 0);
        }
    }

    int ans = 0;

    for (int i = 1; i <= m; ++i)
    {
        if (!bridge[i])
        {
            e[i << 1].open = false;
            e[i << 1 | 1].open = false;

            clear();

            int cur = 1;

            for (int k = 1; k <= n; ++k)
            {
                if (!dfn[k])
                {
                    tarjan(k, 0, cur);
                }
            }

            ans = gcd(ans, cur);

            e[i << 1].open = true;
            e[i << 1 | 1].open = true;
        }
    }

    for (int i = 1; i <= ans; ++i)
    {
        if (ans % i == 0)
        {
            printf("%d ", i);
        }
    }

    return 0;
}