众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的： 勇太有一张$n$个点$m$条边的无向图，每一条边的长度都是1。现在他想再在这张图上连上一条连接两个不同顶点边，使得1号点到$n$号点的最短路尽可能的短。现在他想要知道最短路最短是多少，以及再保证最短路最短的情况下，他有多少种连边的方案。 当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？
数据组数不超过100组。每组数据的第一行两个整数$n,m(2 \leq n \leq 100, 0 \leq m \leq 100)$。 接下来$m$行。每行两个整数$u,v(1 \leq u,v \leq n)$，代表原图中的一条无向边。注意可能有自环和重边。
对于每一组数据输出一行两个整数：最短路最短是多少以及加边的方案数。
2 1 1 2
1 1
你只能连上1 2这条边。