{"raw_statement":[{"iden":"statement","content":"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.\n\nYou 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$.\n\nInitially, $w_i = 0$ for all $i in [ 1, n ]$.\n\nLet'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:\n\nPlease write a program to support these events efficiently.\n\nThe first line of the input contains an integer $T (1 <= T <= 5)$, denoting the number of test cases.\n\nIn 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.\n\nFor the next $n -1$ lines, each line contains two integers $u$ and $v$, denoting a bidirectional edge between vertex $u$ and $v$.\n\nFor the next $m$ lines, each line describes an event.\n\nFor each query event, print a single line containing an integer, denoting the answer.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"For each query event, print a single line containing an integer, denoting the answer."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 50 $.  \n\n**First Problem (Fixed Order)**  \n- $ n $ passengers board in order $ 1, 2, \\dots, n $.  \n- Passenger $ 1 $ (Duha) chooses a seat uniformly at random from $ \\{1, 2, \\dots, n\\} $.  \n- For $ i = 2, \\dots, n $: if seat $ i $ is free, passenger $ i $ takes it; otherwise, chooses uniformly at random from remaining seats.  \n- Let $ P_n $ be the probability that passenger $ n $ sits in seat $ n $.  \n\n**Second Problem (Random Order)**  \n- $ m $ passengers board in a uniformly random permutation of $ \\{1, 2, \\dots, m\\} $.  \n- Passenger $ 1 $ (Duha) chooses a seat uniformly at random from $ \\{1, 2, \\dots, m\\} $.  \n- For each subsequent passenger: if their assigned seat is free, take it; else, choose uniformly at random from remaining seats.  \n- Let $ Q_m $ be the probability that the **last passenger in the boarding order** sits in their assigned seat.  \n\n**Objective**  \nFor each test case, compute:  \n- $ P_n = \\frac{1}{2} $ for $ n \\geq 2 $, and $ P_1 = 1 $.  \n- $ Q_m = \\frac{1}{2} $ for $ m \\geq 2 $, and $ Q_1 = 1 $.","simple_statement":"Duha loses his ticket and picks a random seat. Others take their own seat if available, else pick randomly. Find the probability that the last person gets their own seat in two cases:  \n1. People board in order 1 to n (Duha is 1).  \n2. People board in random order (Duha is still 1).  \n\nGiven n and m, compute both probabilities for each test case.","has_page_source":false}