第一行包含 2 个正整数 N,M，为图的顶点数与边数。

接下来M 行，每行两个正整数 x, y，表示有一条顶点 x 连向顶点 y 的边，请注意可能有自环与重边。

样例解释

1 到 5 的最短路有 4 条，分别为 2 条 1-->2-->4-->5 和 2 条 1-->3-->4-->5（由于 4-->5 的边有 2 条）。

对于 20% 的数据，N ≤ 100；

对于 60% 的数据，N ≤ 1000；

对于 100% 的数据，1≤ N ≤ 100000，0≤ M ≤ 200000 。