Distinct Routes

题目描述

一个游戏由 $n$ 个房间和 $m$ 个传送器组成。每天开始时，你从房间 1 出发，需要到达房间 $n$。 在一局游戏中每个传送器最多使用一次。如果你选择路线最优，你最多可以玩多少天？

输入格式

第一行输入包含两个整数 $n$ 和 $m$：房间数和传送器数。房间编号为 1,2,$\dots$, $n$。 接下来有 $m$ 行，每行描述一个传送器。每行包含两个整数 $a$ 和 $b$：存在一个从房间 $a$ 到房间 $b$ 的传送器。 不存在起点和终点都相同的两条传送器。

输出格式

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

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

提示

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

标签: CSES1711|图论

来源

CSES1711|图论