G. Good but not Excellent
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yugandhar, the owner of Algorithm shop, gave a directed weighted tree containing $$$n$$$ nodes and $$$m$$$ pairs of integers in the form of {$$$x$$$,$$$y$$$} to Vardhan, who is a daily customer and frequents this shop, and asked him to run the following algorithm:

  1. Do the following for every pair of nodes $$$u$$$,$$$v$$$ $$$(1 \le u,v \le n)$$$:
    • if there is a directed edge from $$$u$$$ to $$$v$$$ and there is no directed edge from $$$v$$$ to $$$u$$$, then add a directed edge from $$$v$$$ to $$$u$$$.
  2. Change all edge weights of the tree to $$$1$$$.
  3. Create a variable $$$ans$$$=0.
  4. Do the following for every pair from $$$1$$$ to $$$m$$$ in order:
    • Let Operation 1 be initializing the variable $$$sum1$$$ and $$$sum1$$$ be the sum of the weights of edges on the shortest path from $$$x$$$ to $$$y$$$ on the tree.
    • Let Operation 2 be initializing the variable $$$sum2$$$ and $$$sum2$$$ be the sum of the weights of edges on the shortest path from $$$y$$$ to $$$x$$$ on the tree.
    • If you choose Operation 1 as your good operation for this particular pair, then do $$$ans$$$+=$$$sum1$$$ and change the weights of all edges on the shortest path from $$$x$$$ to $$$y$$$ on the tree to $$$0$$$. Otherwise do $$$ans$$$+=$$$sum2$$$ and change the weights of all edges on the shortest path from $$$y$$$ to $$$x$$$ on the tree to $$$0$$$.

After successfully running this algorithm, Yugandhar asked Vardhan to find the maximum value of variable $$$ans$$$ if he chooses Operation 1 or Operation 2 optimally for every pair from $$$1$$$ to $$$m$$$.

Vardhan got so confused, so please help him to find the required solution.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^{4}$$$). The description of the test cases follows.

The first line of each testcase contains two integers $$$n,m$$$ $$$(1 \le n,m \le 5000)$$$ — the number of nodes in the given tree and the number of pairs of integers.

The next $$$n-1$$$ lines contain two integers $$$u,v$$$ $$$(1 \le u,v \le n, u≠v)$$$ — there is a directed edge from $$$u$$$ to $$$v$$$.

The next line contains $$$m$$$ space separated pairs of integers {$$$x_i$$$,$$$y_i$$$} $$$(1 \le x_i,y_i \le n, x_i≠y_i, 1 \le i \le m)$$$.

It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all testcases doesn't exceed $$$10^{4}$$$.

Output

For each test case, print two lines:

  1. Maximum value of the variable $$$ans$$$.
  2. An array of $$$m$$$ elements, where every element is either $$$1$$$ if you choose Operation 1 as the good operation for that particular pair or $$$2$$$ if you choose Operation 2 as the good operation for that particular pair. If there are multiple arrays which gives the maximum value of $$$ans$$$, then output any.
Example
Input
3
3 1
1 2
1 3
1 2
3 2
1 2
1 3
1 2
1 3
5 3
1 2
4 3
3 1
5 3
2 3
4 5
1 5
Output
1
1
2
1 2
6
1 1 2
Note

In the $$$3^{rd}$$$ testcase, all possible ways to choose operations are:

  1. If you choose operations $$$[1,1,1]$$$ then $$$ans=4$$$.
  2. If you choose operations $$$[1,1,2]$$$ then $$$ans=6$$$.
  3. If you choose operations $$$[1,2,1]$$$ then $$$ans=5$$$.
  4. If you choose operations $$$[2,1,1]$$$ then $$$ans=5$$$.
  5. If you choose operations $$$[2,1,2]$$$ then $$$ans=5$$$.
  6. If you choose operations $$$[2,2,1]$$$ then $$$ans=6$$$.
  7. If you choose operations $$$[1,2,2]$$$ then $$$ans=5$$$.
  8. If you choose operations $$$[2,2,2]$$$ then $$$ans=4$$$.

Hence, the maximum value of $$$ans$$$ is $$$6$$$.