C国的街道

C 国的地图可以看作一棵由 $N$ 个节点组成的树。每个节点代表一座城市，每条边代表连接两座城市的街道。

C 国的街道都平行于坐标轴，因此每座城市最多连接上、下、左、右四个方向的街道，且每个方向至多有一座城市与之相连。

你来到 C 国旅游，希望开车经过尽可能多的街道。然而，频繁转弯会浪费很多时间。一次“转弯”是指在某座城市从水平方向的街道驶入垂直方向的街道，或从垂直方向的街道驶入水平方向的街道。

请找出一条路径，使其满足以下条件：

• 每座城市最多经过一次；
• 转弯次数不超过 $K$；
• 经过的街道数尽可能多。

同时，请求出满足条件且经过街道数最多的不同路径数量。若两条路径经过的城市和街道完全相同，仅行驶方向相反，则视为同一条路径。

输入格式

第一行包含两个整数 $N$ 和 $K$，分别表示城市数量和允许的最大转弯次数。城市编号为 $1$ 至 $N$。

接下来 $N$ 行，第 $i$ 行包含四个整数 $l,d,r,u$，依次表示与城市 $i$ 的左、下、右、上方向相连的城市编号。若某个值为 $0$，则表示城市 $i$ 在对应方向上没有与其他城市相连。

输出格式

输出两个整数。

第一个整数表示满足条件的路径所经过的最大街道数，第二个整数表示达到该最大值的不同路径数量。

样例输入

12 4
0 2 3 4
0 0 0 1
1 0 0 0
5 1 0 0
6 0 4 0
0 7 5 0
8 0 9 6
10 11 7 12
7 0 0 0
0 0 8 0
0 0 0 8
0 8 0 0

样例输出

7 4

数据范围

• $1\le N\le 10^4$；
• $0\le K\le N$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

12 4
0 2 3 4
0 0 0 1
1 0 0 0
5 1 0 0
6 0 4 0
0 7 5 0
8 0 9 6
10 11 7 12
7 0 0 0
0 0 8 0
0 0 0 8
0 8 0 0

输出

7 4