Sum of Scores in Good Permutations of a Tree

You are given a tree with \( n \) vertices and a designated root \( r \). The vertices are labeled from 1 to \( n \). A permutation \( p = (p_1, p_2, \dots, p_n) \) of \( \{1,2,\dots,n\} \) is called good if for every pair of vertices \( u,v \) such that \( u \) is an ancestor of \( v \) in the tree, the index \( a_u \) of \( u \) in the permutation satisfies \( a_u < a_v \).

For a given permutation \( p \), define its score by \[ \text{score}(p)=\sum_{i=1}^{n-1}\left|p_i-p_{i+1}\right|, \] where \( |x| \) denotes the absolute value of \( x \). The task is to compute the sum of scores over all possible different good permutations.

Note: The input tree is given as an undirected tree. The root \( r \) is specified and the tree structure is determined by the unique simple paths. A vertex \( v \) (other than \( r \)) can be placed in the permutation only after its parent is placed. This guarantees the ancestral ordering condition.

inputFormat

The input is given as follows:

 n r
 u1 v1
 u2 v2
 ...
 u(n-1) v(n-1)

The first line contains two integers \( n \) and \( r \) (\( 1 \le n \le 15 \)) where \( n \) is the number of vertices and \( r \) is the root vertex. Each of the next \( n-1 \) lines contains two integers \( u_i \) and \( v_i \) indicating that there is an edge between vertices \( u_i \) and \( v_i \).

outputFormat

Output a single integer: the sum of scores over all good permutations of the tree.

sample

1 1

0