#P18370. Directed Hanoi
Directed Hanoi
Directed Hanoi
Directed Hanoi 的游戏棋盘包含 根柱子,编号为 到 。某些柱子之间有有向边,所有边都从编号较小的柱子指向编号较大的柱子。
初始时,柱子 1 上放有 个大小分别为 到 的圆盘,从下到上按从大到小的顺序叠放。游戏的目标是把所有圆盘移动到柱子 上。
一次移动中,可以取走某根柱子 最上方的圆盘,将它放到另一根柱子 的最上方,但必须同时满足:
- 从 到 存在一条有向路径,不要求存在直接边;
- 柱子 为空,或者其最上方的圆盘比要移动的圆盘大。
这条路径上其他柱子的圆盘状况不影响移动。圆盘可以沿整条可达路径直接从 移到 ,不需要在途中柱子上停留。
给定棋盘,求能够完成游戏目标的最大圆盘数 。可以证明这个最大值一定有限。如果连一个圆盘也无法移到柱子 ,答案为 0。
输入格式
第一行包含两个整数 ,分别表示柱子数和有向边数。
接下来 行,每行包含两个整数 ,表示一条从 指向 的有向边。
输出格式
输出一个整数,表示最多可以从柱子 1 全部移动到柱子 的圆盘数。
数据范围
- ;
- ;
- ;
- 同一对柱子至多在输入中出现一次,不存在重边或自环。
输入只有一组数据。
样例输入 1
5 4
1 2
2 3
3 4
4 5
样例输出 1
5
样例输入 2
6 8
1 2
2 3
3 6
1 4
4 5
5 6
2 5
1 6
样例输出 2
5
样例输入 3
2 0
样例输出 3
0
样例说明
第一个样例中,下面是把5个圆盘从柱子1移动到柱子5的一种过程。每一列是一种状态;Peg i 表示柱子i,同行的数字按从下到上的顺序描述圆盘,空格子表示该柱子为空。

第三个样例没有边,因此一个圆盘也无法移动。