Fan Triangulation Transformation

A convex n-gon comes with an initial triangulation: exactly n-3 diagonals are drawn so that no two cross. The vertices are labeled 1, 2, …, n in counterclockwise order. A fan triangulation with respect to a vertex x is a triangulation in which every diagonal has x as one endpoint (note that the edges of the polygon are not considered diagonals).

In the original triangulation, there are exactly n-3 diagonals, and among these some may already be incident to x. Denote by k the number of diagonals in the given triangulation that have x as an endpoint. Naturally, the fan triangulation with center x should contain exactly all diagonals of the form (x, v) for every vertex v which is not adjacent to x (i.e. excluding the two neighbors of x on the boundary). Thus the target fan contains exactly n-3 diagonals, and the number of diagonals missing (i.e. not currently present) is

[ m = (n-3) - k. ]

Transformation is done by flip operations. In one operation, you remove one diagonal (which will necessarily be one that is not in the final fan triangulation) and then add a new diagonal so that the result is still a triangulation. Each operation is represented as an ordered pair of unordered pairs ((a,b),(c,d)) meaning that the diagonal connecting vertices a and b is removed and the diagonal connecting vertices c and d is added.

It turns out that any flip operation that optimally transforms the triangulation into the fan triangulation will add one of the missing fan diagonals. However the order in which the missing fan diagonals are inserted is not completely arbitrary. In particular, if we list the target set of fan diagonals (i.e. all diagonals of the form (x,v) for every vertex v not adjacent to x) in the order in which their non‑x endpoints appear along the boundary (in counterclockwise order starting from x), then some of these diagonals are already present and the remaining missing ones occur in one or more contiguous blocks. Flips in different blocks can be interleaved arbitrarily, but within each block the relative order is forced by dependency constraints (each missing diagonal can only be added once a unique quadrilateral is available). It can be shown that for a contiguous block of r missing diagonals the number of flip sequences used to add them optimally is equal to the rth Catalan number, namely

[ C(r) = \frac{1}{r+1}\binom{2r}{r}. ]

Since the flips on different blocks are independent and may be interleaved arbitrarily, if the missing diagonals split into t blocks with r₁, r₂, \dots, r_t missing diagonals in each block (so that \( \sum_{i=1}^{t} r_i = m \)), then the total number of optimal flip sequences is given by

[ \frac{m!}{r_1!,r_2!\cdots r_t!} \times \prod_{i=1}^{t} C(r_i) \pmod{10^9+7}. ]

Your task is: given the polygon (with n vertices), a vertex x, and the current triangulation (specified by its n-3 diagonals), determine:

1. The minimum number of flip operations required, m, to convert the current triangulation into the fan triangulation with center x.
2. The number of distinct optimal flip sequences (modulo \(10^9+7\)) that achieve this transformation.

Input Format: The first line contains two integers n and x (3 < n ≤ 10⁵, 1 ≤ x ≤ n). Each of the next n-3 lines contains two integers a and b (1 ≤ a, b ≤ n, a ≠ b) representing a diagonal between vertices a and b in the initial triangulation. It is guaranteed that the set of diagonals forms a valid triangulation of a convex polygon.

Output Format: Output two space‐separated integers on a single line: the minimum number m of flip operations required and the number of optimal flip sequences modulo \(10^9+7\).

Example Explanation:

• Example 1: For a quadrilateral (n = 4), there is only one diagonal. If that diagonal is not incident to x, then we need exactly 1 flip and there is only 1 way to do it.
• Example 2: For a pentagon (n = 5) with vertex x = 1, the target fan diagonals are (1,3) and (1,4). If none of these are present initially (i.e. k = 0) then m = 2. Moreover, since the missing fan diagonals form one contiguous block of length 2, the number of ways is \(\frac{2!}{2!} \times C(2) = 2\). (Recall that \(C(2)=2\)).
• Example 3: For a pentagon with x = 1 where the diagonal (1,3) is already present (k = 1), we have m = 1 and only one way to add the missing diagonal (1,4).

Note: You may assume that the input size is large so efficient I/O and algorithms are required.

inputFormat

The first line contains two integers n and x separated by a space.

Each of the following n-3 lines contains two integers a and b representing a diagonal (an unordered pair).

You may assume that the input always represents a valid triangulation of a convex polygon with n vertices.

outputFormat

Output two integers separated by a space on a single line: the minimum number of flips m and the number of optimal flip sequences modulo \(10^9+7\).

sample

4 1
2 4

1 1