ALT
Contest: Codeforces Round 406 (Div. 1)
Difficulty rating: 3200
Tags: data structures, flows, graphs, trees

ALT is a planet in a galaxy called "Encore". Humans rule this planet but for some reason there's no dog in their planet, so the people there are sad and depressed. Rick and Morty are universal philanthropists and they want to make people in ALT happy.

ALT has n cities numbered from 1 to n and n - 1 bidirectional roads numbered from 1 to n - 1. One can go from any city to any other city using these roads.

There are two types of people in ALT:

1. Guardians. A guardian lives in a house alongside a road and guards the road.
2. Citizens. A citizen lives in a house inside a city and works in an office in another city.

Every person on ALT is either a guardian or a citizen and there's exactly one guardian alongside each road.

Rick and Morty talked to all the people in ALT, and here's what they got:

- There are m citizens living in ALT.
- Citizen number i lives in city number xi and works in city number yi.
- Every day each citizen will go through all roads along the shortest path from his home to his work.
- A citizen will be happy if and only if either he himself has a puppy himself or all of guardians along his path to his work has a puppy (he sees the guardian's puppy in each road and will be happy).
- A guardian is always happy.

You need to tell Rick and Morty the minimum number of puppies they need in order to make all people in ALT happy, and also provide an optimal way to distribute these puppies.

Input format:
The first line of input contains two integers n and m (2 ≤ n ≤ 2 × 104, 1 ≤ m ≤ 104) — number of cities and number of citizens respectively.

The next n - 1 lines contain the roads, i-th line contains endpoint of i-th edge, v and u (1 ≤ v, u ≤ n, v ≠ u).

The next m lines contain the information about citizens. i-th line contains two integers xi and yi (1 ≤ xi, yi ≤ n, xi ≠ yi).

Output format:
In the first line of input print a single integer k, the total number of puppies they need (1 ≤ k ≤ n).

In the second line print an integer q, the number of puppies to give to citizens, followed by q distinct integers a1, a2, ..., aq, index of citizens to give puppy to (0 ≤ q ≤ min(m, k), 1 ≤ ai ≤ m).

In the third line print an integer e, the number of puppies to give to guardians, followed by e distinct integers b1, b2, ..., be, index of road of guardians to give puppy to (0 ≤ e ≤ min(n - 1, k), 1 ≤ bi ≤ n - 1).

Sum of q and e should be equal to k.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
Map of ALT in the first sample testcase (numbers written on a road is its index):

Map of ALT in the second sample testcase (numbers written on a road is its index):

Example input:
4 5
2 4
3 4
1 4
2 4
2 1
2 4
1 2
2 3

Example output:
3
1 5
2 3 1

Example input:
4 7
3 4
1 4
2 1
4 2
4 2
2 4
1 4
2 1
3 1
4 2

Example output:
3
1 6
2 2 3

Editorial:
If n and m were smaller: We construct a bipartite graph. For each citizen we consider a vertex in the first part, and for each guardian in the tree we consider a vertex in the second part. We put an edge between vertex i from first part and j from second part if and only if path xi to yi contains edge j. Answer to the problem is vertex cover of this graph. Time complexity: $${\mathcal {O}}(n^{2}m)$$
But now that n and m are great, we can't use this approach.
We will instead build a DAG. Like above, For each citizen we consider a vertex in the first part, and for each guardian in the tree we consider a vertex in the second part. Consider the data structure that is used to find LCA of two vertices in the tree (keeping 2i-th ancestor of each vertex for each i). We will use that to build the graph.
For each vertex v in the tree and i (0 ≤ i ≤ lg(n)), we consider a vertex in the tree, this vertex is pr(v, i). We'll build a flow network. For each v, we put an edge from pr(v, 0) to the vertex corresponding to edge (guardian) connecting v and its parent (with capacity = ∞). For each i > 0, we put an edge from pr(v, i) to pr(v, i - 1) with capacity = ∞ and one to pr(2i - 1 - th parent of v, i - 1) with capacity = ∞. Then for each citizen, like the algorithm we used to find the LCA of xi and yi, when we're going up from a vertex v to its i-th parent, we put an edge from vertex corresponding to citizen i to pr(v, i) with capacity = 1.
Finally we consider a vertex S as source and T and sink. For each citizen i, we put an edge from S to vertex corresponding to him/her with capacity = 1. And for each guardian put an edge from vertex corresponding to this edge to T with capacity = 1.
It can be shown that the answer to the original problem is maximum flow of this network. Also certificate can be found using a DFS (it's exactly like finding a certificate(vertex cover) in maximum-matching approach).
Since the network contains levels(cuts) from S to T with all edges with capacity equal to 1, the total time complexity is $${\mathcal{O}}(E{\sqrt E})$$ where E is the number of edges in the network which is $${ \mathcal { O } } ( n \lg ( n ) )$$, so:
Time complexity: $${ \mathcal { O } } ( n { \sqrt { n \lg ( n ) } } )$$