Mayoi Hachikuji has a habit of getting lost. The town she resides in can be modeled as a tree of $$$n$$$ nodes with strange weighted edges. Let $$$C_u(v)$$$ denote the weight of the edge from node $$$u$$$ to node $$$v$$$ when accessed from node $$$u$$$ (note that $$$C_u(v)$$$ is not necessarily equal to $$$C_v(u)$$$). When Mayoi is at node $$$u$$$, she will move to some node $$$v$$$ (which is adjacent to node $$$u$$$) with probability $$$\frac{C_u(v)}{\sum\limits_{\text{$$$v'$$$ is adjacent to node $$$u$$$}} C_u(v')}$$$ in $$$1$$$ step.
She has $$$q$$$ queries for you. Each query is in the form $$$s \ t$$$ where she wonders what the expected number of steps to reach node $$$t$$$ if she starts at node $$$s$$$. Since Mayoi isn't particularly good at math (or following directions), help her answer her queries!
The first line of input contains a single integer $$$T$$$ denoting the number of test cases $$$(1 \leq T \leq 3)$$$.
The first line of each test case contains two integers $$$n\ q$$$ denoting the number of nodes in the tree and the number of queries $$$(2 \leq n, q \leq 10^5)$$$.
The following $$$n-1$$$ lines contain four integers $$$u \ v \ C_u(v) \ C_v(u)$$$ denoting that there is an edge from node $$$u$$$ to node $$$v$$$ with cost $$$C_u(v)$$$ when accessed from node $$$u$$$ and cost $$$C_v(u)$$$ when accessed from node $$$v$$$ $$$(1 \leq u \leq v \leq n, 1 \leq C_u(v), C_v(u) \leq 3366)$$$. It is guaranteed that the edges form a tree.
The following $$$q$$$ lines each contain two integers $$$s \ t$$$ denoting the starting and ending nodes of Mayoi's query $$$(1 \leq s, t \leq n)$$$.
—
Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
Test $$$1$$$ satisfies $$$n, q \leq 10$$$.
Tests $$$2 - 3$$$ satisfy $$$n,q \leq 1000$$$.
Tests $$$4 - 5$$$ satisfy $$$t = 1$$$.
Tests $$$6 - 9$$$ satisfy $$$s = 1$$$.
Tests $$$10 - 13$$$ have the tree generated as follows: for each $$$i$$$ from $$$2$$$ to $$$n$$$, there is an edge from node $$$i$$$ to node $$$\lfloor \frac{i}{2} \rfloor$$$.
The remaining tests do not satisfy any additional constraints.
For each query, output a new line containing an integer $$$E$$$, denoting the expected number of steps modulo $$$998244353$$$. Let the answer be $$$\frac{x}{y}$$$. Output $$$E$$$ such that $$$x \equiv E \cdot y \pmod{998244353}$$$.
33 61 2 1 22 3 2 11 21 32 12 33 23 13 71 2 1 22 3 3 41 21 32 12 33 23 11 15 41 2 3 41 3 5 42 5 1 12 4 2 41 21 34 15 1
1 4 3 3 1 4 1 332748121 4 332748120 1 5 0 332748122 299473309 499122180 499122180
Problem Idea: dutin
Problem Preparation: 3366
Occurrences: Advanced 7
