Berland 的 “InterCity Jets”（ICJ）公司运营 $n$ 个城市之间的航班。在 ICJ 的时刻表中，总共有 $m$ 条双向航线。每条航线连接两个城市，并且保证可以使用 ICJ 的航线在任意两个城市之间飞行（允许零次或多次转机）。

每个城市的机场由 $m$ 个航站楼组成。航站楼用 $1$ 到 $m$ 的整数编号。每条航线的起飞和降落航站楼是预先确定的，这意味着一条航线由两个“城市和该城市机场的航站楼 ID”对来指定。请注意，某些航站楼可能不会出现在 ICJ 的时刻表中，因为 Berland 还有其他航空公司。

如果在转机过程中，到达的航班和起飞的航班安排在不同的航站楼，那么为了避免重复的安全检查，乘客将乘坐摆渡车进行运送。如果是在同一个航站楼转机，则通过廊桥进行转机。

著名旅游博主 Oblomov 计划乘坐 ICJ 的飞机从城市 $s$ 到城市 $f$。Oblomov 不喜欢坐摆渡车，而且由于他旅行中的所有航班都由 ICJ 赞助，他首先希望最小化航站楼之间转机时乘坐摆渡车的次数（即跨航站楼转机的次数）。只有在有多种最少摆渡车次数的选择时，他才计划最小化航班的总数。

给定 ICJ 的航班时刻表，以及旅程的起点和终点城市，确定 Oblomov 从起点城市到终点城市最少需要乘坐摆渡车的次数，以及在满足该最少摆渡车次数的情况下，他最少需要乘坐的航班数量。在起点和终点城市，由于 Oblomov 乘出租车出行，他可以选择任意航站楼。

输入格式

第一行包含四个整数 $n, m, s$ 和 $f$（$2 \le n \le 10^5$，$n-1 \le m \le 2 \cdot 10^5$，$1 \le s, f \le n$，$s \ne f$）—— 分别表示城市的数量、ICJ 时刻表中的航线数量，以及 Oblomov 的起点和终点城市。

接下来的 $m$ 行，每行包含一条双向航线的描述，由四个整数 $a_i, ta_i, b_i, tb_i$（$1 \le a_i, b_i \le n$，$1 \le ta_i, tb_i \le m$，$a_i \ne b_i$）组成 —— 分别表示该航线连接的第一座机场编号、第一座机场的航站楼编号、第二座机场编号以及第二座机场的航站楼编号。

你可以认为可以通过 ICJ 在任意两个城市之间飞行，并且任意两座机场之间直接连接的 ICJ 航线不超过一条。

输出格式

输出两个整数 —— Oblomov 在旅途中最少需要乘坐摆渡车的次数，以及在满足该最少摆渡车次数的情况下，最少需要乘坐的航班数量。

样例

输入样例 1

3 3 3 1
1 1 2 1
3 1 2 2
1 2 3 3

输出样例 1

0 1