第1题：

有n 个恶魔降临了...小S 决定打击这些恶魔，她的魔法能在一瞬间同时杀死任意数量的恶魔，但是有些恶魔之间存在保护关系，比如恶魔A保护恶魔B，则如果A 不死则B 不受伤害，现在小S 想知道最少需要使用多少次魔法才能杀死所有恶魔，如果不能杀死所有恶魔，输出-1。

1 打怪兽.in

1 打怪兽.out


输入

第一行两个个正整数n和m 分别表示恶魔数和保护关系对数。

接下来m 行每行两个数A 和B 描述一对保护关系。


输出

一行一个整数表示答案。


输入样例 1 

3 2
1 2
3 2
输出样例 1

2
提示

20%的数据：n≤10；

40%的数据：n≤100；

60%的数据：n≤1000；

80%的数据：n≤10000；

第2题：

2220年，维斯特洛大陆的交通极其发达，人们旅行的时候可以通过每个城市中心的瞬时传送站直接从一个城市传送到任意其他城市，传送时间忽略不计，但是因为传送站的运转非常耗电，所以每个传送站每天只能针对其他每个城市各启动一次，并且每个传送站每次启动的时间都是不相同的，任意两个传送站的每次启动时间也不相同。维斯特洛大陆一共有n个城市，现在给出每个城市的传送站针对其他城市的启动时间，请你帮忙算出对于每一对城市来说，如果想在一天之内从城市a到达城市b，那么最早什么时间能到达目标城市b？

注意：如果一个人打算从城市a到达城市c，然后再从城市c到达城市b。而当他到从a到达c之后，c到b的传送站启动时间还没有到，那么他就在城市c一直等到从c到b的传送站启动之后再被传送到b城市。反之如果当他从a到到达c之后，发现从c到b的传送站已经启动过了，那么他是不能通过c到达b的。

2 未来城市.in

2 未来城市.out


输入

输入第一行是一个整数n，表示城市的个数。

接下来是n行n列的矩阵，第i行第j列的数字
A
i
,
j
A 
i,j
​
 表示从城市i到城市j的传送站启动时间。传送站自己不会对自己传送，所以用0表示。


输出

输出也是一个n行n列的矩阵，第i行第j列的数字表示从城市i到城市j的最早到达时间。


输入样例 1 

3
0 4 5
2 0 3
1 6 0
输出样例 1

0 4 5
2 0 3
1 4 0
提示

对于20%的数据，n<=10

对于40%的数据，n<=20

对于60%的数据，n<=50

对于100%的数据，n<=500,
A
i
,
j
A 
i,j
​
 <=
1
0
9
10 

第3题：

为了防止鬼子进村扫荡，游击队号召每个村的老乡在平原地下共同挖出一个四通八达的地道，把所有村庄都连通起来，每个村庄分布在如下图所示的棋盘格式的地图中某些行列交叉的位置，现在给出每个村庄的坐标，每个村的老乡从自己村开始挖，每天可以向四周各扩散一个位置，当两个村某天扩散到同一个交叉点位置时，说明这两个村的地道就通了，但是只要还剩1个村没有联通，其他村就会一直这样挖下去，那么多少天之后所有村的地道都能连通起来？

QQ图片20220210001757.png

3 地道战.in

3 地道战.out


输入

输入第1行一个整数n，表示共有n个村庄

接下来n行，每行两个整数Xi，Yi，表示第i个村庄的坐标。


输出

输出一行一个整数，表示让所有村庄都能连通的天数


输入样例 1 

2
1 1
6 6
输出样例 1

5
提示

对于20%的数据，满足1≤N≤5; 1≤Xi,Yi≤50;

对于100%的数据，满足1≤N≤50; 1≤Xi,Yi≤
1
0
9
10 
9
 。