「BZOJ1064」[NOI2008]假面舞会

Description

一年一度的假面舞会又开始了,栋栋也兴致勃勃的参加了今年的舞会。今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一 个自己喜欢的面具。每个面具都有一个编号,主办方会把此编号告诉拿该面具的人。为了使舞会更有神秘感,主办方把面具分为k(k3)k (k\ge 3)类,并使用特殊的技术将每个面具的编号标在了面具上,只有戴第ii类面具的人才能看到戴第i+1i+1类面具的人的编号,戴第kk类面具的人能看到戴第11 类面具的人的编号。 参加舞会的人并不知道有多少类面具,但是栋栋对此却特别好奇,他想自己算出有多少类面具,于是他开始在人群中收集信息。 栋栋收集的信息都是戴第几号面具的人看到了第几号面具的编号。如戴第22号面具的人看到了第55号面具的编号。栋栋自己也会看到一些编号,他也会根据自己的面具编号把信息补充进去。由于并不是每个人都能记住自己所看到的全部编号,因此,栋栋收集的信 息不能保证其完整性。现在请你计算,按照栋栋目前得到的信息,至多和至少有多少类面具。由于主办方已经声明了k3k\ge 3,所以你必须将这条信息也考虑进去。

Input

第一行包含两个整数n,mn, m,用一个空格分隔,nn 表示主办方总共准备了多少个面具,mm 表示栋栋收集了多少条信息。接下来mm行,每行为两个用空格分开的整数a,ba, b,表示戴第aa号面具的人看到了第bb号面具的编号。相同的数对a,ba, b在输入文件中可能出现多次。

Output

包含两个数,第一个数为最大可能的面具类数,第二个数为最小可能的面具类数。如果无法将所有的面具分为至少33类,使得这些信息都满足,则认为栋栋收集的信息有错误,输出两个1-1

Sample Input

1
2
3
4
5
6
6 5
1 2
2 3
3 4
4 1
3 5

Sample Output

1
2
3
4
3 3
1 2
2 1
2 3

HINT

100%100\%的数据,满足n100000,m1000000n \leq 100000, m \leq 1000000

Solution

反向边连边权为1-1,正向边边权为11
判断是否有正向边的环,有的话。
答案就是每个联通块里的环的gcdgcd,链上的可以不用管,因为可以任意取。
没有的话,说明只有链,那么就是所有联通块里的最长链长之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 120000*3, M = 2100000*2;
struct Edge {
int u, v, nxt, w;
}e[M * 2];
int head[N], en;
void addedge(int x, int y, int z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].w = z;
}
int n, m;
int ans1, ans2, d[N];
bool fg;
int vis[N];
void dfs(int x) {
if(fg) return;
vis[x] = 1;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(vis[y] == 1) fg = 1;
else
dfs(y);
}
vis[x] = 2;
}
int gcd(int x, int y) {
if(!y) return x;
return gcd(y, x % y);
}
void solve(int x, int F) {
vis[x] = 1;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
if(vis[y] == 1) {
int t = abs(d[x] - d[y] + e[i].w);
ans1 = gcd(ans1, t);
}
else if(!vis[y]){
d[y] = d[x] + e[i].w;
solve(y, x);
}
}
vis[x] = 2;
}

int mx, mn;
void get(int x) {
mx = max(mx, d[x]);
mn = min(mn, d[x]);
vis[x] = 1;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(vis[y]) continue;
d[y] = d[x] + e[i].w;
get(y);
}
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
int x = read(), y = read();
addedge(x, y, 1);
}
for(int i = 1; i <= n;++i) if(!vis[i]) dfs(i);
for(int i = 1; i <= m; ++i)
addedge(e[i].v, e[i].u, -1);
memset(vis,0,sizeof vis);
if(fg) {
for(int i = 1; i <= n; ++i) if(!vis[i]) solve(i, 0);
for(int i = 3; i <= ans1; ++i) if(ans1 % i == 0) {
ans2 = i;
break;
}
printf("%d %d\n",ans1, ans2);
} else {
for(int i = 1; i <= n; ++i) if(!vis[i]) {
mx = mn = 0;
get(i);
ans1 += mx - mn + 1;
}
if(ans1 < 3) {
puts("-1 -1");
return 0;
} else printf("%d 3\n",ans1);
}
return 0;
}