Bay

문제

We have a grid (lattice) graph $G(n,n)G(n,\; n)$, where $nn$ is the number of vertices along both the $xx$-axis and the $yy$-axis, that is, the number of rows and columns. The vertices of the graph $G(n,n)G(n,\; n)$ are numbered consecutively from $11$ to $n^{2}n^2$ in row-major ordering; starting from the top-left vertex, we traverse row by row from top to bottom, and within each row from left to right. Figure 1 shows two examples, $G(5,5)G(5,\; 5)$ and $G(7,7)G(7,\; 7)$ with vertex numbers.

Figure 1. Left: Grid graph $G(5,5)G(5,5)$. Right: $G(7,7)G(7,7)$.

We are given a spanning tree $TT$ of $G(n,n)G(n,\; n)$. The left in Figure 2 shows a spanning tree $TT$ of $G(7,7)G(7,\; 7)$. If we add an edge of $G(n,n)G(n,\; n)$ that does not belong to $TT$ (called non-tree edge), then exactly one simple cycle is created. We define the region enclosed by this cycle as a bay. There is a one-to-one correspondence between non-tree edges and bays, that is, each non-tree edge corresponds to exactly one bay. The area of a bay is defined by number of $1\times 11\; \backslash times\; 1$ unit cells enclosed by the cycle. The right in Figure 2 shows two bays(colored blue and orange) created by adding two non-tree edges $(u,v)(u,\; v)$ and $(p,q)(p,\; q)$, respectively. Note that the areas of two bays created by $(u,v)(u,\; v)$ and $(p,q)(p,\; q)$ are $44$ and $1212$, respectively.

Figure 2. A spanning tree $TT$ of a grid $G(7,7)G(7,\; 7)$ and two bays created by $(u,v)(u,\; v)$ and $(p,q)(p,\; q)$.

Given a spanning tree $TT$ of a grid graph $G(n,n)G(n,\; n)$ and a positive integer $SS$, write a program that finds all non-tree edges that creates bays of area $SS$ and outputs the first non-tree edge among them in lexicographical order.

입력

Your program is to read from standard input. The input starts with a line containing two integers $nn$ and $SS$ where 5 &le; n &le; 300 for $G(n,n)G(n,\; n)$ and 1 &le; S &le; (n &minus; 1)^2. Each of the following n^2 &minus; 1 lines contains two distinct integers $uu$ and $vv$ representing an edge $(u,v)(u,\; v)$ of a spanning tree $TT$, where 1 &le; u < v &le; n^2.

출력

Your program is to write to standard output. The first line should contain the number of non-tree edges that create the bays of area $SS$. The second line should contain two distinct integers $uu$ and $vv$ () representing the first non-tree edge $(u,v)(u,\; v)$ in lexicographical order among those that create the bays of area $SS$. The lexicographical order of two edges $(a,b)(a,\; b)$ and $(c,d)(c,\; d)$ is defined such that $(a,b)(a,\; b)$ comes before $(c,d)(c,\; d)$ if and only if or, if $a=ca\; =\; c$ then . If there is no non-tree edge that creates the bay of area $SS$, then print “0” in the first line and two zeros “0 0” in the second line.

Figure 3 shows two spanning trees of a grid graph with $n=5n\; =\; 5$, which are the sample inputs and outputs.

Figure 3. Two spanning trees of $G(5,5)G(5,\; 5)$ for Sample Input 1 and 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
11 16
12 17
13 14
14 15
15 20
16 21
17 18
17 22
18 23
19 20
19 24
24 25

2
13 18

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

0
0 0