题目描述

给定一个有向图，包含 $n$ 个点和 $m$ 条边。每条边的代价均为 $1$，也就是说，沿一条边走需要 $1$ 分钟。

两个“表兄弟”从同一个起点 $S$ 出发。其中一个人想要到达点 $A$，另一个人想要到达点 $B$。

他们一开始必须一起走，直到他们第一次形成循环：也就是在共同走过的路径中，第一次到达某个已经到达过的点。设这个第一次被第二次到达的点为 $Z$。

在形成循环之后，两个人可以分开继续走；如果他们愿意，也可以继续走相同的路。也就是说，从点 $Z$ 开始，不再强制要求两人同行。

每个人都必须在形成循环之后才结束自己的路程。不过，如果形成循环的位置恰好就是 $A$ 或 $B$，那么对应的人可以不再继续走，也就是后续路径长度可以为 $0$。

如果两人第一次形成循环恰好发生在 $t$ 分钟后，随后第一个人从 $Z$ 到 $A$ 还需要 $t_A$ 分钟，第二个人从 $Z$ 到 $B$ 还需要 $t_B$ 分钟，那么这个方案的用时为：

$$\max(t+t_A,t+t_B).$$

请你求这个值的最小可能值；在第二类任务中，还需要构造达到最小值的三段路径。

任务类型

输入第一行给出一个整数 $c$，表示任务类型：

• 若 $c=1$，只需要输出最小的 $\max(t+t_A,t+t_B)$；
• 若 $c=2$，需要输出三段路径：
  1. 两人共同从 $S$ 走到 $Z$ 的路径；
  2. 形成循环后，第一个人从 $Z$ 到 $A$ 的路径；
  3. 形成循环后，第二个人从 $Z$ 到 $B$ 的路径。

这三段路径对应的值 $\max(t+t_A,t+t_B)$ 必须最小。

输入格式

第一行包含一个整数 $c$。

第二行包含两个整数 $n,m$。

第三行包含三个整数 $S,A,B$。

接下来 $m$ 行，每行包含两个整数 $X,Y$，表示存在一条从 $X$ 指向 $Y$ 的有向边。

输出格式

若 $c=1$，输出一个整数，表示最小的 $\max(t+t_A,t+t_B)$。

若 $c=2$，输出三条路径。每条路径占两行：

• 第一行输出路径长度，即路径中的边数；
• 第二行输出路径经过的所有点，点之间用空格分隔。

第一条路径应当是从 $S$ 到 $Z$ 的共同路径，并且它的最后一个点 $Z$ 必须是这条共同路径中第一次重复出现的点。第二条路径应当从 $Z$ 到 $A$。第三条路径应当从 $Z$ 到 $B$。

数据范围

• $1\le S,A,B,Z\le n\le 5000$；
• 点编号为 $1$ 到 $n$；
• $A\ne B$；
• $1\le m\le n(n-1)$；
• 保证每个测试数据至少存在一个解；
• 不存在自环；
• 任意两个不同点之间最多存在一条有向边；
• 如果两人在 $A$ 分开，第一个人可以不再移动，此时第二段路径长度为 $0$，路径只包含点 $A$；对 $B$ 同理；
• 对每个子任务，$c=1$ 的测试点占该子任务分数的 $60\%$。

子任务

子任务	分值	限制
1	30	$n\le 500$，$m=n$，且所有边均为 $i\to (i\bmod n)+1$
2	50	$n\le 500$
3	20	$n\le 5000$ 且 $m\le 4n$

样例 1

输入

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

输出

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

样例 2

输入

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

输出

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

样例 3

输入

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

输出

4
1 2 3 4 3
0
3
1
3 5

样例 4

输入

1
4 4
1 2 4
1 3
3 2
2 3
2 4

输出

5

样例图示

样例1图解