You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1711 题。

题目描述

游戏中有 $n$ 个房间和 $m$ 个传送门。每天开始时，你从房间 $1$ 出发，必须到达房间 $n$。

在游戏过程中，你每个传送门至多使用一次。你能玩多少天，假设你选择的路径是最优的？

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示房间的数量和传送门的数量。房间编号为 $1,2,…,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 \leq n \leq 500$；

$2 \leq m \leq 1000$；

$1 \leq a, b \leq n$。