链接: https://cses.fi/problemset/task/1711

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一个游戏由 $n$ 个房间和 $m$ 个传送器组成。每天开始时，你从房间 $1$ 出发，必须到达房间 $n$。

在游戏过程中，每个传送器至多可以使用一次。如果你最优地选择路线，最多能玩多少天？

输入

第一行输入包含两个整数 $n$ 和 $m$：房间数量和传送器数量。房间编号为 $1,2,\dots,n$。

之后有 $m$ 行描述传送器。每行包含两个整数 $a$ 和 $b$：存在一条从房间 $a$ 到房间 $b$ 的传送器。

没有两条传送器的起点和终点相同。

输出

先输出一个整数 $k$：你最多能玩的天数。然后按样例输出 $k$ 条路线描述。你可以输出任意合法解。

数据范围

$2 \le n \le 500$ $1 \le m \le 1000$ $1 \le a,b \le n$

样例输入

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

样例输出

2
3
1 2 6
4
1 3 4 6