我们有一个网格图 $G(n, n)$，其中 $n$ 是 $x$ 轴和 $y$ 轴上的顶点数，即行数和列数。图 $G(n, n)$ 的顶点按行优先顺序从 1 到 $n^2$ 编号；从左上角的顶点开始，逐行从上到下遍历，在每一行内从左到右遍历。图 1 展示了两个示例 $G(5, 5)$ 和 $G(7, 7)$ 及其顶点编号。

图 1. 左：网格图 $G(5, 5)$。右：$G(7, 7)$。

给定 $G(n, n)$ 的一棵生成树 $T$。图 2 左侧展示了 $G(7, 7)$ 的一棵生成树 $T$。如果我们添加一条不属于 $T$ 的 $G(n, n)$ 边（称为非树边），则会恰好形成一个简单环。我们将该环所围成的区域定义为“湾”（bay）。非树边与湾之间存在一一对应关系，即每一条非树边对应恰好一个湾。湾的面积定义为该环所围成的 $1 \times 1$ 单位格的数量。图 2 右侧展示了通过添加两条非树边 $(u, v)$ 和 $(p, q)$ 所形成的两个湾（分别用蓝色和橙色标出）。注意，由 $(u, v)$ 和 $(p, q)$ 形成的两个湾的面积分别为 4 和 12。

图 2. 网格 $G(7, 7)$ 的一棵生成树 $T$ 以及由 $(u, v)$ 和 $(p, q)$ 形成的两个湾。

给定网格图 $G(n, n)$ 的生成树 $T$ 和一个正整数 $S$，编写一个程序，找出所有形成面积为 $S$ 的湾的非树边，并输出其中字典序最小的那条非树边。

输入格式

程序从标准输入读取数据。输入的第一行包含两个整数 $n$ 和 $S$，其中 $5 \le n \le 300$（对应 $G(n, n)$），$1 \le S \le (n - 1)^2$。接下来的 $n^2 - 1$ 行，每行包含两个不同的整数 $u$ 和 $v$，表示生成树 $T$ 的一条边 $(u, v)$，其中 $1 \le u < v \le n^2$。

输出格式

程序向标准输出写入数据。第一行应包含形成面积为 $S$ 的湾的非树边的数量。第二行应包含两个不同的整数 $u$ 和 $v$ ($u < v$)，表示在所有形成面积为 $S$ 的湾的非树边中，字典序最小的那条边 $(u, v)$。两条边 $(a, b)$ 和 $(c, d)$ 的字典序定义为：当且仅当 $a < c$ 或者 $a = c$ 且 $b < d$ 时，$(a, b)$ 排在 $(c, d)$ 之前。如果没有形成面积为 $S$ 的湾的非树边，则第一行输出“0”，第二行输出“0 0”。

图 3 展示了 $n = 5$ 时网格图的两棵生成树，它们分别是样例输入和输出对应的图。

图 3. 样例输入 1 和 2 中 $G(5, 5)$ 的两棵生成树。

样例

输入 1

5 2
1 2
2 3
3 8
4 5
5 10
6 11
7 8
7 12
8 13
9 10
9 14
11 12
11 16
12 17
13 14
14 15
15 20
16 21
17 18
17 22
18 23
19 20
19 24
24 25

输出 1

2
13 18

输入 2

5 2
1 2
2 3
3 8
4 5
5 10
6 11
7 8
7 12
8 13
9 10
9 14
11 12
13 14
14 15
15 20
16 17
16 21
17 18
17 22
18 23
19 20
19 24
23 24
24 25

输出 2

0
0 0