Ants
Contest: Codeforces Round 497 (Div. 1)
Difficulty rating: 3200
Tags: 2-sat, data structures, trees

There is a tree with $$$n$$$ vertices. There are also $$$m$$$ ants living on it. Each ant has its own color. The $$$i$$$-th ant has two favorite pairs of vertices: ($$$a_i, b_i$$$) and ($$$c_i, d_i$$$). You need to tell if it is possible to paint the edges of the tree in $$$m$$$ colors so that every ant will be able to walk between vertices from one of its favorite pairs using only edges of his color; if it is possible, you need to print which pair every ant should use.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of vertices.

Each of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), meaning that there is an edge between vertices $$$u_i$$$ and $$$v_i$$$.

The next line contains a single integer $$$m$$$ ($$$1 \leq m \leq 10^4$$$) — the number of ants.

Each of the next $$$m$$$ lines contains four integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, and $$$d_i$$$ ($$$1 \leq a_i, b_i, c_i, d_i \leq n$$$, $$$a_i \neq b_i, c_i \neq d_i$$$), meaning that pairs ($$$a_i$$$, $$$b_i$$$) and ($$$c_i$$$, $$$d_i$$$) are favorite for the $$$i$$$-th ant.

Output format:
Print "NO" (without quotes) if the wanted painting is impossible.

Otherwise, print "YES" (without quotes). Print $$$m$$$ lines. On the $$$i$$$-th line, print $$$1$$$ if the $$$i$$$-th ant will use the first pair and $$$2$$$ otherwise. If there are multiple answers, print any.

Constraints:
Time limit: 3.0 s
Memory limit: 768.0 MB

Note:
In the sample, the second and the third edge should be painted in the first color, the first and the fifth should be painted in the second color, and the fourth should be painted in the third color.

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

Example output:
YES
2
1
2

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

Example output:
NO

Editorial:
Slow solution.
We need to choose one of two paths for each ant so that they will not contain a common edge. Let's make a 2-SAT, and for each ant, we will create two contrary vertices: one will denote that we take the first path, and another will denote that we take the second path. Then for every two paths which share an edge, we add a condition that they can't be taken together. Now we just need to check that the 2-SAT has a solution.
The complexity is $$$O(n m^2)$$$.
First solution.
Let's build a binary tree with $$$m$$$ leaves for each edge. Each vertex of the tree will be associated with some vertex of the 2-SAT. The vertex of the tree which covers leaves from $$$l$$$ to $$$r$$$ will be associated with a vertex of the 2-SAT which says if the edge should be painted with a color from $$$l$$$ to $$$r$$$. To build a vertex which is associated with a leaf we just need to add for every path of the ant which covers the current edge a condition which tells that if we take this path, then this vertex is true. And for every non-leaf vertex of the tree we need to add three conditions. First and second: if any of the vertices associated with the two sons is true, then the vertex associated with the current vertex is also true ($$$l\rightarrow v$$$, $$$r\rightarrow v$$$). And third: both vertices associated with the two sons can't be true ($$$l\rightarrow !r$$$).
The trees will be persistent, which means that if the vertex we want already exists, we will reuse it.
Now we will build such trees recursively. First for the children, and then for the current edge. To build a tree for a new edge we first take an empty tree, then for each child, we recursively merge its tree with the current. If during the merge one of the vertices is empty, we return the second vertex. Then we add the paths which end in the current vertex.
You have to be careful not to add the edges which will not be present in the final tree. For example, you can first build a tree, and then go through the new vertices one more time and add the edges.
Then as in the previous solution, we check if there is a solution of this 2-SAT.
It can be shown that for a vertex of the binary tree which covers $$$k$$$ leaves there will be created no more than $$$8k$$$ instances of this vertex, because there are at most $$$4k$$$ ends of the paths connected with these leaves and at most $$$8k - 1$$$ vertices which are the LCA of some set of these vertices. Now if we summarize it over all the vertices of the binary tree, we get approximately $$$8 m \log(m)$$$.
So the total complexity is $$$O(m \log(m))$$$
Second solution.
Let $$$L = 64$$$ be the number of bits in a machine word.
Let's calculate a matrix $$$2m \times 2m$$$ of ones and zeros, where cell $$$(i, j)$$$ is filled with $$$1$$$ iff the paths $$$i$$$ and $$$j$$$ have a common edge. We will store this matrix as an array of bitsets.
Let's run a DFS which for every edge will return a set of paths that cover it. We will store such sets in a map from number of block to a bitmask of length $$$L$$$. We recursively calculate the sets for the children. Also for every path which starts in the vertex, we make a set containing only this path. Then if some sets share the same path, we remove it from both. Then we merge them by always adding the smaller map to the larger. While doing so we iterate over the elements of the smaller map and over the blocks of the larger map and add a block of edges to the matrix. For now, it is enough to add each edge to the matrix only in one direction. It can be shown that it works in $$$O \left( m \log^2(m) + m^2 \cdot \frac{\log(L)}{L} \right)$$$.
Now we want to transpose the matrix and add it to itself to make it complete. To do it we divide it into blocks $$$L \times L$$$, and transpose them one by one, then swap the blocks. Here is how we transpose a block.
Assume $$$L = 2^K$$$. We will make $$$K$$$ iterations. On the $$$i-th$$$ iteration we will divide the block into subblocks $$$2^i \times 2^i$$$ and in each block, we will swap the top right quarter and the bottom left quarter. Each iteration can be performed in $$$O(L)$$$. We can prove by induction that after $$$i$$$ iterations each subblock $$$2^i \times 2^i$$$ will be transposed.
This step works in $$$O \left( m^2 \cdot \frac{\log(L)}{L} \right)$$$.
It is easy to get a bitset of straight edges and a bitset of reversed edges of the 2-SAT for every vertex using this matrix. Now if we store the visited vertices in a bitset, we can implement the 2-SAT algorithm in $$$O \left( \frac{m^2}{L} \right)$$$.
The total complexity is $$$O \left( m \log^2(m) + m^2 \cdot \frac{\log(L)}{L} \right)$$$.