#P18370. Directed Hanoi

Directed Hanoi

Directed Hanoi

Directed Hanoi 的游戏棋盘包含 NN 根柱子,编号为 11 到 NN。某些柱子之间有有向边,所有边都从编号较小的柱子指向编号较大的柱子。

初始时,柱子 1 上放有 KK 个大小分别为 11 到 KK 的圆盘,从下到上按从大到小的顺序叠放。游戏的目标是把所有圆盘移动到柱子 NN 上。

一次移动中,可以取走某根柱子 AA 最上方的圆盘,将它放到另一根柱子 BB 的最上方,但必须同时满足:

  • 从 AA 到 BB 存在一条有向路径,不要求存在直接边;
  • 柱子 BB 为空,或者其最上方的圆盘比要移动的圆盘大。

这条路径上其他柱子的圆盘状况不影响移动。圆盘可以沿整条可达路径直接从 AA 移到 BB,不需要在途中柱子上停留。

给定棋盘,求能够完成游戏目标的最大圆盘数 KK。可以证明这个最大值一定有限。如果连一个圆盘也无法移到柱子 NN,答案为 0。

输入格式

第一行包含两个整数 N,MN,M,分别表示柱子数和有向边数。

接下来 MM 行,每行包含两个整数 ai,bia_i,b_i,表示一条从 aia_i 指向 bib_i 的有向边。

输出格式

输出一个整数,表示最多可以从柱子 1 全部移动到柱子 NN 的圆盘数。

数据范围

  • 2≤N≤5002\le N\le500;
  • 0≤M≤N(N−1)/20\le M\le N(N-1)/2;
  • 1≤ai<bi≤N1\le a_i<b_i\le N;
  • 同一对柱子至多在输入中出现一次,不存在重边或自环。

输入只有一组数据。

样例输入 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,同行的数字按从下到上的顺序描述圆盘,空格子表示该柱子为空。

第一个样例的搬盘过程

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