题目描述

给定有向图G(V, E)， 图中所有边权值为1，给定源点(起点)s，终点t，求s->t 的最短路长度。

输入格式

第一行包含4个整数n, m, s, t表示图共有n个节点和m条有向边。(n<=5000, m<=200000)。 起点为s， 终点为t。 接下来m行，每行包含3个整数u, v, 1表示从u到v的一条权值为1的有向边。

输出格式

输出共1行。 输出最短路的长度。 若无法到达，输出“No path”。

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

2

数据规模与约定