【题目背景】 奥术飞弹是一个非指向性的技能，在施法前可以指定弹道，并对路径上第一个碰撞的目标造成伤害。 作为一颗成熟的奥术飞弹，你应该学会自己决定用于攻击目标的最短路径，并且 100% 命中目标。 【题目描述】 Meowowco 正在玩一款未知的 1 v 1 RTS 游戏，游戏创建后会随机创建一个有 n 个房间的地图，由 m 条通道相连，房间与房间之间最多只有一个通道，直接由通道相连的房间的距离可以记为 1，整张地图 所有房间两两可达。 Meowowco 出生在编号为 1 的房间，而她的对手出生在编号为 n 的房间。现在 Meowowco 需要创造军 队或者释放技能去击败对手，不过今天她有着更高级的黑魔法加持（指自瞄），令"奥术飞弹"变成"成熟 的奥术飞弹"，只释放"奥术飞弹"就可以获得胜利。 作为一颗成熟的奥术飞弹，不管当前处于哪个房间，都会瞬间规划好 一条 前往目标所在位置的最短飞 行弹道（当然，最短飞行弹道有时候并不是唯一的，所以有多条最短飞行弹道时会随机选择一条），如 果它没有沿着当前房间规划好的最短飞行弹道飞行，记为偏离轨迹 1 次。 作为一颗成熟的奥术飞弹，应该会自己计算一条有着“大可能性“的飞行弹道。由于有些房间的最短飞行 弹道不唯一，飞行弹道可能偏离也可能不偏离，”大可能性”飞行弹道要求 可能产生的偏离数尽可能大： 一个房间如果有多条通往目标的最短飞行弹道，则可能偏离数增加 1，目标是找到有最多这样房间 的飞行弹道。 下面将举个栗子来解释它： 对这个地图来说：

它有 3 条从 1 到 6 的最短飞行弹道： 1 => 2 => 4 => 6 1 => 3 => 4 => 6 1 => 3 => 5 => 6 假如你现在处于房间 1，那么你可以选择房间 2 和房间 3 ，因为 2 和 3 都在最短飞行弹道上，所以不 管前往哪个房间都会让可能偏离数增加，此时可能偏离数为 1； 当飞弹选择 1=>2 时，接下来它只能沿着 2 => 4 => 6，飞行，因此这条弹道的可能偏离数为 1。 当飞弹选择 1 => 3 时,接下来的房间 4 和 5 都处于最短飞行弹道上，不管前往哪个房间都会让可能偏离 数增加，此时可能偏离数增加到 2；之后都只有一条弹道到达 6，因此这两条弹道的可能偏离数为 2。 综上所述， 1 => 2 => 4 => 6 的可能偏离数为 1。 1 => 3 => 4 => 6 的可能偏离数为 2。 1 => 3 => 5 => 6 的可能偏离数为 2。 最大的可能偏离数为 2。 寻找出所有的最短飞行弹道，每条最短飞行弹道都有一个可能偏离数，找到其中最大的可能偏离数，输 出最短飞行弹道条数和最大的可能偏离数。 简而言之，就是 n 个点的无向连通图，无重边和自环，目标是从 1 点到达 n 点。在一个点上，如果有 多条最短路径到达终点，则 可能偏离数 加一，求出最短路径的总条数，以及所有最短路中可能偏离数 的最大值。 【输入格式】 从文件 missiles.in 中读取数据 第一行输入两个正整数 n 和 m，表示房间个数和通道个数。 接下来 m 行，每行包含两个正整数 u, v，表示房间 u 到房间 v 存在一条通道。 【输出格式】 输出到文件 missiles.out 中 输出最短飞行弹道条数和最大的可能偏离数，由于最短飞行弹道的条数可能很大，请对 998244353 取 模。 【输入样例 1】 6 7 1 2 3 4 2 4 1 3 3 5 4 6 5 6 【输出样例 1】 3 2 【输入样例 2】 7 8 1 2 1 3 3 4 2 4 4 5 4 6 5 7 6 7 【输出样例 2】 4 2 【数据范围与约定】 对于测试点 1 ∼ 5：1 ≤ n ≤ 10。 对于测试点 6 ∼ 10：1 ≤ n ≤ 50。 对于测试点 11 ∼ 15：1 ≤ n ≤ 1000。 对于测试点 16 ∼ 20：1 ≤ n ≤ 100000。 对于 100% 的数据：n − 1 ≤ m ≤ 2 × n，保证图连通。