Interstellar Federation – Star Gate Arrangements

The Interstellar Federation consists of \(N\) planets (numbered \(1\) to \(N\)). In our universe, the planets are connected by exactly \(N-1\) bidirectional interstellar channels forming a tree; hence any two planets are reachable. In addition, there exist \(D\) parallel universes (numbered \(1\) to \(D\)) that are identical copies of our universe (which is numbered \(0\)). For every \(i\) with \(0 \le i .

Once all star gates are ready, the federation flagship Batthyány begins its maiden voyage. It starts orbiting \(P_1^0\) (planet \(1\) in universe \(0\)). Captain Ágnes (the first player) and Lieutenant Gábor (the second player) play a game: they take turns choosing the next destination. The next planet must be directly reachable by an interstellar channel (which are bidirectional) or by a star gate (which is one‐way) from the current planet. However, each planet may be visited at most once in a given universe (but note that the same planet number in a different universe is considered distinct). If a player cannot choose a legal destination on his/her turn, that player loses.

Both players are absolutely perfect and know the layout of all interstellar channels and star gates. Your task is to count the number of ways to set up the star gates (i.e. the choices of \(A_i\) and \(B_i\) for all \(0 \le i < D\)) so that Captain Ágnes (the first player) wins the game, assuming both play optimally. Two star gate arrangements are considered different if there exists an index \(i\) such that \(A_i\) or \(B_i\) differs.

Game Analysis

For each universe, the game is played on the same tree. Let \(f(u)\) denote the outcome (winning or losing) of the tree game without star gates when starting at planet \(u\) with only \(u\) visited. More formally, when arriving at planet \(u\) (with a given parent which is considered visited),\footnote{For a vertex \(u\) with parent \(p\) the recurrence is defined as \(f(u,p)=\mathsf{true}\) if there exists a neighbor \(v\neq p\) with \(f(v,u)=\mathsf{false}\), and \(f(u,p)=\mathsf{false}\) if no such neighbor exists. In particular, when no parent is present (i.e. a fresh start), we define \(f(u,0)\) as the outcome.} we have

[ f(u, p)=\begin{cases}\text{true} & \text{if }\exists v\in \Gamma(u)\setminus{p} \text{ such that } f(v,u)=\text{false},\ false & \text{otherwise.} \end{cases} ]

In our game with star gates the state is a pair ((i,u)) meaning that we are in universe (i) at planet (u) (with a fresh start on the tree, i.e. only (u) is visited in that universe).

Without star gates the outcome would be (f(u,0)). In the full game, however, if a star gate is built from planet (u) in universe (i) (i.e. if (A_i=u)), then an extra move is available: from (u) one may teleport to (P_{B_i}^{i+1}). Notice that the move using the star gate is available even if the tree move alone would give a losing position. In fact the recurrence for the full game outcome (H(i,u)) is given by

[ H(i,u)= \begin{cases} f(u,0) & \text{if } u\neq A_i,\[1mm] f(u,0) \lor \lnot H(i+1, B_i) & \text{if } u = A_i, \end{cases} ]

with the base case (H(D,u)= f(u,0)) (since there is no star gate in universe (D)).

In particular, the starting state is ((0, P_1^0)) and Captain Ágnes wins if and only if (H(0,1)) is true. Notice that if (f(1,0)) (which we abbreviate as (f(1))) is already true then the outcome is winning regardless of star gate choices. Otherwise, if (f(1)) is false, the only chance to flip the outcome is to activate the star gate at planet (1) in universe (0) (i.e. by choosing (A_0=1)) and then carefully choose (B_0) so that the teleport leads to a state where the second player loses. With some combinatorial analysis (using the fact that the tree is fixed and identical in all universes) one may show that the final answer can be computed as follows.

Define \(a\) as the number of planets for which \(f(u)\) is true and \(b=N-a\) as the number of planets for which \(f(u)\) is false. Also, let \(T=N^2\) be the total number of possible choices \((A_i, B_i)\) for a single star gate. Then:

• If \(f(1)\) is true then the first player wins regardless, so the answer is \(T^D\).
• If \(f(1)\) is false then one must force teleportation in universe 0, and after a delicate recursion (described in the analysis) the answer equals a certain quantity \(G(0)\) computed by the recurrences below.

For \(0\le i\le D\) let \(G(i)\) be the number of star gate arrangements from universes \(i\) to \(D-1\) that yield a winning outcome for the current player when starting at a planet \(u\) with \(f(u)=false\) (and let \(F(i)\) be the arrangements that yield losing outcome). In particular, when \(i=D\) we have \(G(D)=0\) (and \(F(D)=1\)). For \(0\le i

[ F(i)= (N-1)\cdot N \cdot T^{D-i-1} + \Bigl(a\cdot T^{D-i-1} + b\cdot G(i+1)\Bigr),\qquad G(i)= T^{D-i} - F(i). ]

Thus, if \(f(1)\) is false the final answer is \(G(0)\), and if \(f(1)\) is true the answer is \(T^D\). Your task is to compute and output the final answer as an integer (the numbers can be huge so use arbitrary‐precision arithmetic if necessary).

---

Input Format

Output Format

---

Sample Input 1

2 1
1 2

Sample Output 1

4

Explanation

---

Sample Input 2

3 1
1 2
2 3

Sample Output 2

2

Explanation

inputFormat

The first line contains two integers \(N\) and \(D\) separated by a space.

The next \(N-1\) lines each contain two integers \(u\) and \(v\), representing a bidirectional interstellar channel between planets \(u\) and \(v\).

\(N\) is the number of planets and \(D\) is the number of star gate layers (i.e. the number of star gates, one between each adjacent universe pair).

outputFormat

Output a single integer – the number of star gate arrangements for which the first player wins when both players play optimally.

sample

2 1
1 2

4