Professor Elephant is a master of data structure. Recently, he invented a perfect data structure to maintain information on a tree. He is very proud of this invention, so he prepared this problem for you.
You are given a tree with $n$ nodes. The tree nodes are numbered from $1$ to $n$. The $i$-th node has an integer value $w_i$.
Initially, $w_i = 0$ for all $i in [ 1, n ]$.
Let's denote $p (u, v)$ as all nodes $x$ on the shortest path from the $u$-th node to the $v$-th node(include $u$ and $v$). There will be $m$ events of $7$ kinds below:
Please write a program to support these events efficiently.
The first line of the input contains an integer $T (1 <= T <= 5)$, denoting the number of test cases.
In each test case, there are two integers $n, m (1 <= n <= 500000, 1 <= m <= 2000)$ in the first line, denoting the number of nodes and events.
For the next $n -1$ lines, each line contains two integers $u$ and $v$, denoting a bidirectional edge between vertex $u$ and $v$.
For the next $m$ lines, each line describes an event.
For each query event, print a single line containing an integer, denoting the answer.
## Input
The first line of the input contains an integer $T (1 <= T <= 5)$, denoting the number of test cases.In each test case, there are two integers $n, m (1 <= n <= 500000, 1 <= m <= 2000)$ in the first line, denoting the number of nodes and events.For the next $n -1$ lines, each line contains two integers $u$ and $v$, denoting a bidirectional edge between vertex $u$ and $v$.For the next $m$ lines, each line describes an event.
## Output
For each query event, print a single line containing an integer, denoting the answer.
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq n, m \leq 50 $.
**First Problem (Fixed Order)**
- $ n $ passengers board in order $ 1, 2, \dots, n $.
- Passenger $ 1 $ (Duha) chooses a seat uniformly at random from $ \{1, 2, \dots, n\} $.
- For $ i = 2, \dots, n $: if seat $ i $ is free, passenger $ i $ takes it; otherwise, chooses uniformly at random from remaining seats.
- Let $ P_n $ be the probability that passenger $ n $ sits in seat $ n $.
**Second Problem (Random Order)**
- $ m $ passengers board in a uniformly random permutation of $ \{1, 2, \dots, m\} $.
- Passenger $ 1 $ (Duha) chooses a seat uniformly at random from $ \{1, 2, \dots, m\} $.
- For each subsequent passenger: if their assigned seat is free, take it; else, choose uniformly at random from remaining seats.
- Let $ Q_m $ be the probability that the **last passenger in the boarding order** sits in their assigned seat.
**Objective**
For each test case, compute:
- $ P_n = \frac{1}{2} $ for $ n \geq 2 $, and $ P_1 = 1 $.
- $ Q_m = \frac{1}{2} $ for $ m \geq 2 $, and $ Q_1 = 1 $.