IIT

Problem

Find the probability to reach the target node from the root node 1 in an unweighted undirected tree in time t. In each second you can visit one of the unvisited nodes from the current node with equal probability, and if there are no unvisited nodes, you can stay at the same node. The tree is given in the form of an adjacency list.

Input

• n: The number of nodes in the tree.
• edges: A list of edges in the tree, where each edge is represented as a pair of nodes.
• target: The target node.
• t: The time.

Output

• The probability to reach the target node from the root node 1 in time t.

Constraints

• 1 <= n <= 100
• 0 <= t <= n
• 1 <= target <= n
• The tree is unweighted and undirected.
• The tree is given in the form of an adjacency list.