## BFS before DFS solution codechef

Alice and Bob live in a country in which there are $N$ cities (numbered from $1$ to $N$) connected to each other using $N−1$ bidirectional roads in such a way that any two cities are reachable from each other.

This country has a special property: for each city in the country, there are **at most** $6$ roads directly connected to it.

Alice and Bob both decide to go on a tour of the country, starting from city number $1$. Alice uses Depth First traversal (DFS) order to travel through all the $N$ cities while Bob uses Breadth First Traversal (BFS) order. At any city, if there is more than one possibility for the next city to be visited, then each option is equally likely to be chosen by both Alice and Bob.

The pseudocode of their respective traversals are as follows:

```
// Alice's DFS traversal
dfs(u):
// Let C denote the set of children of u
shuffle(C)
// Let the current state of C be [C[1], C[2], ..., C[k]]
for i from 1 to k:
dfs(C[i])
```

```
// Bob's BFS traversal
queue Q
Q.push(1)
while Q is not empty:
u = front(Q)
pop(Q)
// Let C denote the set of children of u
shuffle(C)
// Let the current state of C be [C[1], C[2], ..., C[k]]
for i from 1 to k:
Q.push(C[i])
```

Define the *index* of a city in some traversal order to be the number of distinct cities visited before that city during that traversal. Find the expected number of cities whose index in Bob’s traversal is **strictly less** than its index in Alice’s traversal.

It can be shown that this expected value can be expressed as a fraction $QP $, where $P$ and $Q$ are coprime integers, $P≥0$, $Q>0$ and $Q$ is coprime with $998244353$. You should compute $(P⋅Q_{−1})(mod998244353)$, where $Q_{−1}$ denotes the multiplicative inverse of $Q$ modulo $998244353$.

## BFS before DFS solution codechef

### Input Format

- The first line of input will contain a single integer $T$, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integers $N$ — the number of cities.
- The next $N−1$ lines describe the roads. The $i$-th of these $N−1$ lines contains two space-separated integers $u_{i}$ and $v_{i}$, denoting a road between cities $u_{i}$ and $v_{i}$.

### Output Format

For each test case, output on a new line $(P⋅Q_{−1})(mod998244353)$.

### Constraints

- $1≤T≤50$
- $1≤N≤200$
- $1≤u_{i},v_{i}≤N$
- Each city has at most $6$ roads directly connected to it.
- The sum of $N$ over all test cases won’t exceed $300$.

## BFS before DFS solution codechef

### Sample 1:

2 4 1 2 1 4 2 3 5 1 2 1 3 1 4 3 5

249561089 332748119

### Explanation:

## BFS before DFS solution codechef

**Test case $1$:** There are two possible DFS traversals : $[1,2,3,4]$ and $[1,4,2,3]$. Also, there are two possible BFS traversals : $[1,2,4,3]$ and $[1,4,2,3]$.

- Probability that Bob reaches city $1$ before Alice = $0$
- Probability that Bob reaches city $2$ before Alice = $41 $
- Probability that Bob reaches city $3$ before Alice = $0$
- Probability that Bob reaches city $4$ before Alice = $21 $

Therefore, the required expected value is $41 +21 =43 $, which is $249561089(mod998244353)$