原題見(jiàn)
這里（BZOJ和BSOJ都掛了，真杯具，只能借助RQ了囧……）
難度不是很大，就是特殊情況比較多，比較猥瑣（不過(guò)本題數(shù)據(jù)弱，就算不考慮所有的特殊情況也能過(guò)7個(gè)點(diǎn)）。
首先O(NM)的樸素算法很好想到：枚舉K，然后給每個(gè)結(jié)點(diǎn)編號(hào)即可。在編號(hào)時(shí)，先隨便指定一個(gè)未編號(hào)的點(diǎn)，設(shè)它的編號(hào)為0，然后遍歷所有和它相關(guān)聯(lián)的邊（這里可以把原圖想象成一個(gè)無(wú)向圖），將這些邊的另一個(gè)端點(diǎn)編上號(hào)即可，中間若某個(gè)點(diǎn)的編號(hào)出現(xiàn)矛盾，則這個(gè)K不合法，否則這個(gè)K合法。
然后進(jìn)行優(yōu)化：合法的K實(shí)際上是有限制的，它必然是某個(gè)數(shù)的因數(shù)，具體來(lái)說(shuō)，對(duì)這個(gè)圖進(jìn)行DFS，并考察其中所有的跨越邊和逆向邊，對(duì)于跨越邊<i, j>，設(shè)遍歷樹(shù)中i、j間距離為D，則合法的K必然是(D-1)的因數(shù)（因?yàn)閕和遍歷樹(shù)中j的父結(jié)點(diǎn)都有指向j的邊，它們的編號(hào)應(yīng)相同，而它們之間的距離為(D-1)）；對(duì)于逆向邊<i, j>，設(shè)遍歷樹(shù)中i、j間距離為D'，則合法的K必然是(D'+1)的因數(shù)（因?yàn)檫@里形成了一個(gè)環(huán)，環(huán)的長(zhǎng)度為(D'+1)）。這樣一來(lái)就明顯縮小了K的取值范圍，再進(jìn)行枚舉，就可以顯著縮短時(shí)間。
下面是一些極其猥瑣的特殊情況：
（1）根據(jù)題意，必須是K類每類都有，因此在嘗試編號(hào)成功（沒(méi)有發(fā)生任何矛盾）后，還要看一下
實(shí)際出現(xiàn)的編號(hào)數(shù)目是否等于K，若小于K，同樣不合法；
（2）該圖的基圖可能不連通，此時(shí)對(duì)于其基圖的每個(gè)連通塊，其編號(hào)互不影響，所以要對(duì)每個(gè)連通塊分別統(tǒng)計(jì)實(shí)際出現(xiàn)的編號(hào)數(shù)目，設(shè)它們的和為SUM，則不大于SUM的K值均合法（只要中間不出現(xiàn)矛盾），因此可以直接得到最大值為SUM，提前結(jié)束；不過(guò)，這種特判只有在總共實(shí)際出現(xiàn)的編號(hào)數(shù)目小于K的情況下才能進(jìn)行；
（3）由于考察的是實(shí)際出現(xiàn)的編號(hào)數(shù)目，因此最后求出的最大值、最小值可能小于3，這時(shí)應(yīng)作出如下處理：若最大值小于3，則無(wú)解；若最小值小于3，則將最小值改為3。
本題比較猥瑣的數(shù)據(jù)是第4、5、6個(gè)點(diǎn)，分別出現(xiàn)了上述的第（1）、（2）、（3）種特殊情況，此外，這三個(gè)點(diǎn)建出的圖中竟然沒(méi)有一條跨越邊或逆向邊！
代碼：
#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;
}