原题见
这里（BZOJ和BSOJ都挂了，真杯具，只能借助RQ了囧……）
难度不是很大，就是特殊情况比较多，比较猥琐（不过本题数据弱，就算不考虑所有的特殊情况也能过7个点）。
首先O(NM)的朴素算法很好想到：枚举K，然后给每个结点编号即可。在编号时，先随便指定一个未编号的点，设它的编号为0，然后遍历所有和它相关联的边（这里可以把原图想象成一个无向图），将这些边的另一个端点编上号即可，中间若某个点的编号出现矛盾，则这个K不合法，否则这个K合法。
然后进行优化：合法的K实际上是有限制的，它必然是某个数的因数，具体来说，对这个图进行DFS，并考察其中所有的跨越边和逆向边，对于跨越边<i, j>，设遍历树中i、j间距离为D，则合法的K必然是(D-1)的因数（因为i和遍历树中j的父结点都有指向j的边，它们的编号应相同，而它们之间的距离为(D-1)）；对于逆向边<i, j>，设遍历树中i、j间距离为D'，则合法的K必然是(D'+1)的因数（因为这里形成了一个环，环的长度为(D'+1)）。这样一来就明显缩小了K的取值范围，再进行枚举，就可以显著缩短时间。
下面是一些极其猥琐的特殊情况：
（1）根据题意，必须是K类每类都有，因此在尝试编号成功（没有发生任何矛盾）后，还要看一下
实际出现的编号数目是否等于K，若小于K，同样不合法；
（2）该图的基图可能不连通，此时对于其基图的每个连通块，其编号互不影响，所以要对每个连通块分别统计实际出现的编号数目，设它们的和为SUM，则不大于SUM的K值均合法（只要中间不出现矛盾），因此可以直接得到最大值为SUM，提前结束；不过，这种特判只有在总共实际出现的编号数目小于K的情况下才能进行；
（3）由于考察的是实际出现的编号数目，因此最后求出的最大值、最小值可能小于3，这时应作出如下处理：若最大值小于3，则无解；若最小值小于3，则将最小值改为3。
本题比较猥琐的数据是第4、5、6个点，分别出现了上述的第（1）、（2）、（3）种特殊情况，此外，这三个点建出的图中竟然没有一条跨越边或逆向边！
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
const int MAXN = 100000, MAXM = 1100001;
struct edge {
int a, b, s, pre, next;
} E0[MAXM], E[MAXM + MAXM];
int n, m0, m, P, len, X[MAXN], No[MAXN], stk[MAXN], st[MAXN], dep[MAXN], V[MAXN], fo[MAXN], Q[MAXN], res0, res1;
bool vst[MAXN], T0[MAXN];
long long T[MAXN], _Z = 0;
void init_d()
{
re(i, n) E[i].a = E[i].pre = E[i].next = E0[i].a = E0[i].pre = E0[i].next = i;
m0 = n; if (n % 2) m = n + 1; else m = n;
}
void add_edge(int a, int b)
{
E0[m0].a = a; E0[m0].b = b; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
E[m].a = a; E[m].b = b; E[m].s = 1; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
E[m].a = b; E[m].b = a; E[m].s = -1; E[m].pre = E[b].pre; E[m].next = b; E[b].pre = m; E[E[m].pre].next = m++;
}
void init()
{
freopen("party.in", "r", stdin);
int _m, a, b; scanf("%d%d", &n, &_m); init_d();
re(i, _m) {
scanf("%d%d", &a, &b);
add_edge(--a, --b);
}
fclose(stdin);
}
int gcd(int a, int b)
{
int r;
while (b) {
r = a % b; a = b; b = r;
}
return a;
}
void prepare()
{
int tp, x, y, ord = 0;
bool fd;
re(i, n) V[i] = 0; P = 0;
re(i, n) if (!V[i]) {
stk[tp = 0] = i; fo[i] = ord++; V[i] = 1; st[i] = E0[i].next; dep[i] = 0;
while (tp >= 0) {
x = stk[tp]; fd = 0;
for (int p=st[x]; p != x; p=E0[p].next) {
y = E0[p].b;
if (!V[y]) {
stk[++tp] = y; fo[y] = ord++; V[y] = 1; st[y] = E0[y].next; dep[y] = dep[x] + 1; st[x] = E0[p].next; fd = 1; break;
} else if (V[y] == 1) P = gcd(P, dep[x] - dep[y] + 1); else if (fo[y] > fo[x]) P = gcd(P, dep[y] - dep[x] - 1);
}
if (!fd) {V[x] = 2; tp--;}
}
}
len = 0; re3(i, 3, n) if (!(P % i)) X[len++] = i;
}
int test(int K)
{
re(i, n) {vst[i] = 0; No[i] = -1;}
re(i, K) T0[i] = 0;
int x, y, No0, sum = 0, sum0 = 0;
re(i, n) if (!vst[i]) {
No[i] = 0; Q[0] = i; vst[i] = 1; _Z++; if (T[0] != _Z) {T[0] = _Z; sum++;} if (!T0[0]) {T0[0] = 1; sum0++;}
for (int front=0, rear=0; front<=rear; front++) {
x = Q[front];
for (int p=E[x].next; p != x; p=E[p].next) {
y = E[p].b; No0 = No[x] + E[p].s;
if (No0 == K) No0 = 0; else if (No0 == -1) No0 = K - 1;
if (No[y] >= 0 && No0 != No[y]) return -1; else {
No[y] = No0;
if (T[No0] != _Z) {T[No0] = _Z; sum++;}
if (!T0[No0]) {T0[No0] = 1; sum0++;}
}
if (!vst[y]) {vst[y] = 1; Q[++rear] = y;}
}
}
}
if (sum0 < K) res0 = sum;
return sum0;
}
void solve()
{
int K, K0; res0 = res1 = -1;
re(i, len) {
K = X[i]; K0 = test(K);
if (K0 != -1) {
if (res1 == -1) res1 = K0;
if (K0 < K) break; else res0 = K;
}
}
if (res0 < 3) res0 = res1 = -1; else if (res1 < 3) res1 = 3;
}
void pri()
{
freopen("party.out", "w", stdout);
printf("%d %d\n", res0, res1);
fclose(stdout);
}
int main()
{
init();
prepare();
solve();
pri();
return 0;
}