Neighbour Ordering
Contest: CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 3500
Tags: constructive algorithms, graphs

Given an undirected graph $$$G$$$, we say that a neighbour ordering is an ordered list of all the neighbours of a vertex for each of the vertices of $$$G$$$. Consider a given neighbour ordering of $$$G$$$ and three vertices $$$u$$$, $$$v$$$ and $$$w$$$, such that $$$v$$$ is a neighbor of $$$u$$$ and $$$w$$$. We write $$$u <_{v} w$$$ if $$$u$$$ comes after $$$w$$$ in $$$v$$$'s neighbor list.

A neighbour ordering is said to be good if, for each simple cycle $$$v_1, v_2, \ldots, v_c$$$ of the graph, one of the following is satisfied:

- $$$v_1 <_{v_2} v_3, v_2 <_{v_3} v_4, \ldots, v_{c-2} <_{v_{c-1}} v_c, v_{c-1} <_{v_c} v_1, v_c <_{v_1} v_2$$$.
- $$$v_1 >_{v_2} v_3, v_2 >_{v_3} v_4, \ldots, v_{c-2} >_{v_{c-1}} v_c, v_{c-1} >_{v_c} v_1, v_c >_{v_1} v_2$$$.

Given a graph $$$G$$$, determine whether there exists a good neighbour ordering for it and construct one if it does.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq m \leq 3 \cdot 10^5$$$), the number of vertices and the number of edges of the graph.

The next $$$m$$$ lines each contain two integers $$$u, v$$$ ($$$0 \leq u, v < n$$$), denoting that there is an edge connecting vertices $$$u$$$ and $$$v$$$. It is guaranteed that the graph is connected and there are no loops or multiple edges between the same vertices.

The sum of $$$n$$$ and the sum of $$$m$$$ for all test cases are at most $$$3 \cdot 10^5$$$.

Output format:
For each test case, output one line with YES if there is a good neighbour ordering, otherwise output one line with NO. You can print each letter in any case (upper or lower).

If the answer is YES, additionally output $$$n$$$ lines describing a good neighbour ordering. In the $$$i$$$-th line, output the neighbours of vertex $$$i$$$ in order.

If there are multiple good neigbour orderings, print any.

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

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

Example output:
YES
1 2 
4 2 0 
0 1 3 
2 4 
3 1 
YES
1 
0 
NO

Editorial:
First, note that, for each vertex $$$v$$$, the relative order between neighbours that belong to different biconnected components (i. e., neighbours $$$u$$$ and $$$w$$$ so that the edges $$$vu$$$ and $$$vw$$$ belong to different biconnected components) is irrelevant, since there can not be any (vertex-disjoint) cycle using edges from different biconnected components. Therefore, a good ordering for the entire graph will be possible if and only if a good ordering for each of the biconnected components is possible, and if so the ordering for the entire graph can be obtained from the orderings for each of the components by arbitrarily merging the lists of each component for each vertex (preserving the relative order for the lists of each component). Therefore, from now on we will assume that the graph is biconnected. Also, we assume that the graph has at least 3 vertices to avoid trivialities.
Lemma 1: If the graph $$$G$$$ has a cycle $$$\mathcal{C}$$$, and there are two vertices $$$u, v \in \mathcal{C}$$$ not adjacent in the cycle such that there is a path from $$$u$$$ to $$$v$$$ that passes through a vertex $$$w \not\in \mathcal{C}$$$, then the graph $$$G$$$ can not have a good ordering.
Proof: Assume the graph has a good ordering, and label the vertices of the cycle $$$v_1, v_2, \ldots, v_n$$$ so that $$$v_i \leq_{v_{i+1}} v_{i+2}$$$ and $$$u = v_1$$$ and $$$v = v_j$$$ with $$$j \neq 1, 2, n$$$. Let the path between $$$v_j$$$ and $$$v_1$$$ be $$$v_j, w_1, \ldots, w_p$$$, where $$$w_p = v_1$$$, $$$p > 1$$$, and we can assume that all $$$w_i$$$ lie outside the cycle. Considering the cycle $$$v_1, v_2, \ldots, v_j, w_1, \ldots$$$, we can see that since $$$v_1 \leq_{v_2} v_3$$$, it must happen too that $$$ v_j \leq_{w_1} w_2$$$. Now, considering the cycle $$$w_p, \ldots, w_1, v_j, v_{j+1}, \ldots, v_n$$$, we see that since $$$v_j \leq_{v_{j+1}} v_{j+2}$$$ (with possibly $$$v_{j+2} = v_1$$$), we must have $$$w_2 \leq_{w_1} v_j$$$. Since $$$w_2 \neq v_j$$$, we can't have the inequality both ways and we reach a contradiction. $$$\square$$$
Theorem: If the (biconnected) graph $$$G$$$ has a good ordering, then it has a hamiltonian cycle.
Proof: Assume it doesn't have a hamiltonian cycle. Since it is biconnected with at least 3 vertices, it must have some cycle. Let $$$v_1, \ldots, v_c$$$ be a longest cycle of the graph. Because the cycle does not visit all the vertices of the graph and the graph is connected, there must be some vertex $$$u$$$ not in the cycle which is a neighbour of a vertex $$$v_i$$$ in the cycle. Because the graph is biconnected, there must be some path $$$w_1, \ldots, w_d$$$ not passing through $$$v_i$$$ with $$$w_1 = u$$$ and $$$w_d = v_j$$$, a vertex in the cycle. We can choose the path so that vertices $$$w_1, \ldots, w_{d-1}$$$ are not in the cycle, since we can just finish the path at the first vertex that is in the cycle. Now we consider two cases:
• Case 1: $$$v_i$$$ and $$$v_j$$$ are adjacent in the cycle (i. e. $$$j = i+1$$$ or $$$j = i-1$$$, where we admit taking indices modulo $$$c$$$). Now we can consider the cycle $$$v_1, \ldots, v_i, w_1, \ldots, w_{d-1}, v_j, \ldots, v_c$$$, which is strictly longer than the original cycle, but we said it was a longest cycle, contradiction.
• Case 2: $$$v_i$$$ and $$$v_j$$$ are not adjacent in the cycle. Assume $$$i < j$$$ and consider the cycle $$$v_1, \ldots, v_i, w_1, \ldots, w_{d-1}, v_j, \ldots, v_c$$$. We have a path $$$v_i, v_{i+1}, \ldots, v_j$$$ that passes through vertices not in the cycle, so by the first lemma it is not possible to have a good ordering, contradiction.
Now, let's see how we can compute this hamiltonian cycle efficiently. The argument we used in the proof already gives a good algorithm: we find a cycle, and repeatedly find paths that go out of the cycle and then return to it. We will either find a path which returns to an adjacent vertex and therefore we can use it to augment the cycle (Case 1) or we will find that it is impossible to have a good ordering and halt (Case 2). However, implementing this directly is in worst case $$$O(n^2)$$$. We will find a way to implement this idea in $$$O(n)$$$ time, using properties of the DFS tree.
Lemma 2: In a DFS tree of a (biconnected) graph $$$G$$$ with a good ordering, each vertex can have at most two children.
Proof: Suppose that some vertex $$$u$$$ has more than two children. Because the graph is biconnected, we have $$$u$$$ can not be the root, and that from each of the child subtrees there is a back edge to a proper ancestor of $$$u$$$. Let $$$v_1,v_2, v_3$$$ be three children of $$$u$$$ that have back edges (in their respective subtrees) to three vertices $$$w_1, w_2, w_3$$$ with $$$\text{depth}(w_1) \leq \text{depth}(w_2) \leq \text{depth}(w_3)$$$, where $$$\text{depth}$$$ is the depth in the DFS tree. Consider the cycle $$$v_1, u, v_2, \ldots, w_2, \ldots, w_1, \ldots$$$ (goes back to $$$v_1$$$) and the path $$$w_2, \ldots, w_3, \ldots, v_3, u$$$ between $$$w_2$$$ and $$$u$$$, two non-adjacent vertices in the cycle. This contradicts lemma 1. $$$\square$$$
Lemma 3: In a DFS tree of a (biconnected) graph $$$G$$$ with a good ordering, consider a vertex $$$u$$$ that is not the root and whose parent $$$v$$$ is not the root either with two children $$$u_1$$$ and $$$u_2$$$, and let $$$\text{Low}(u_i)$$$ be the vertex with least depth that can be reached with a back edge from the subtree of $$$u_i$$$. Then there is exactly one $$$i$$$ such that $$$\text{Low}(u_i) = v$$$
Proof: Assume that $$$\text{Low}(u_1)$$$ and $$$\text{Low}(u_2)$$$ are both proper ancestors of $$$v$$$ (they can not be descendants of $$$v$$$ since the graph is biconnected). Then, if we consider the cycle which includes the path $$$u_1, u, u_2$$$ and then cycles back using back edges without passing through $$$v$$$, we have a contradiction with lemma 1 considering the path from some vertex in the cycle which is a proper ancestor of $$$v$$$ to $$$u$$$ going down the DFS tree. Therefore, at least one of $$$\text{Low}(u_1)$$$ or $$$\text{Low}(u_2)$$$ is equal to $$$v$$$.
Now let's see that it can not happen that $$$\text{Low}(u_1) = \text{Low}(u_2) = v$$$. Assume that it is the case. Since the graph is biconnected, we must have that $$$\text{Low}(u) \neq v$$$ since it must be a proper ancestor of $$$v$$$ (note that here we are using that $$$v$$$ is not the root). Therefore, since the two children subtrees don't have back edges to vertices higher than $$$v$$$, $$$u$$$ must have a back edge to $$$\text{Low}(u)$$$. Consider the cycle $$$u, u_1, \ldots, v, \text{parent(v)}, \ldots, \text{Low(u)}$$$. Now with the path $$$u, u_2, \ldots, v$$$ lemma 1 is violated. $$$\square$$$
Lemma 4: In a DFS tree of a (biconnected) graph $$$G$$$ with a good ordering, consider a vertex $$$u$$$ that is not the root with parent $$$v$$$ and with only one child $$$u_1$$$. If $$$\text{Low}(u_1) \neq \text{Low}(u)$$$, then $$$\text{Low}(u_1) = v$$$.
Proof: Consider the cycle $$$u, u_1, \ldots, \text{Low}(u_1), \ldots$$$. If $$$u_1$$$ and $$$\text{Low}(u_1)$$$ are not adjacent, the path $$$u, \text{Low}(u), \ldots, \text{Low}(u_1)$$$ violates lemma 1. $$$\square$$$
Theorem: In a DFS tree of a (biconnected) graph $$$G$$$ with a good ordering, we can partition the front edges into:
• One path of the form $$$u_1, \ldots, u_p$$$, where $$$u_{i+1}$$$ is the parent of $$$u_i$$$ for $$$1 \leq i < p$$$, and $$$u_p$$$ is the root, and there is a back edge between $$$u_1$$$ and $$$u_p$$$.
• Some paths of the form $$$u_1, \ldots, u_p$$$, where $$$u_{i+1}$$$ is the parent of $$$u_i$$$ for $$$1 \leq i < p$$$, and there is a back edge between $$$u_1$$$ and the parent of $$$u_p$$$.
Proof: Let $$$u$$$ be a vertex which is not the root. We say that the representative back edge associated with vertex $$$u$$$ is the back edge from $$$u$$$'s subtree that goes to $$$\text{Low}(u)$$$: if there are multiple such back edges, we choose the one that has as the other vertex the one that has a highest DFS visitation number. We partition the front edges $$$(u, \text{parent}(u))$$$ into groups with the same representative edge associated with $$$u$$$. We have to prove that this partition has the desired properties.
Let $$$u, v$$$ be vertices with the same representative edge. One vertex must be an ancestor of the other (otherwise their subtrees would be disjoint and they can not have the same back edges), and every vertex in the path going from one to the other in the tree has the same representative edge (if there was some better edge, the higher vertex would have it as a representative). This proves that the groups form paths of the form $$$u_1, \ldots, u_p$$$, where $$$u_{i+1}$$$ is the parent of $$$u_i$$$ for $$$1 \leq i < p$$$ (note that here $$$u_1, \ldots, u_{p-1}$$$ would be the vertices with the same representative edge but $$$u_p$$$ wouldn't; $$$u_p$$$ is in the path because the partition is of edges, not vertices, and $$$(u_{p-1}, \text{parent}(u_{p-1}))$$$ is an edge in the group).
Now, let's see the other property. It is clear that $$$u_1$$$, the vertex with most depth of the path, has the representative edge of the path as one of its back edges. Now consider $$$u_p$$$. We have multiple cases:
1. $$$u_p$$$ is not the root and it has only one child $$$u_{p-1}$$$. Then since it doesn't have the same representative edge necessarily it must have a back edge and $$$\text{Low}(u_p) \neq \text{Low}(u_{p-1})$$$. By lemma 4, we must have $$$\text{Low}(u_{p-1}) = \text{parent}(u_{p})$$$ and the back edge from $$$u_1$$$ goes to the parent of $$$u_p$$$, as desired.
2. $$$u_p$$$ is not the root, its parent is not the root either, and it has two children, one of which is $$$u_{p-1}$$$. Then by lemma 3, exactly one of the two children has its Low value equal to the parent of $$$u_p$$$. If it were not $$$u_{p-1}$$$, then $$$u_p$$$ would have the same representative edge as $$$u_{p-1}$$$, which is not possible since it is the endpoint of the path. Therefore again we have $$$\text{Low}(u_{p-1}) = \text{parent}(u_{p})$$$, and the back edge from $$$u_1$$$ goes to the parent of $$$u_p$$$.
3. $$$u_p$$$ is the child of the root and it has two children. Now we must have once again $$$\text{Low}(u_{p-1}) = \text{parent}(u_{p})$$$ once again because there is no other vertex with least depth than the parent of $$$u_p$$$, and the back from $$$u_1$$$ goes to the parent of $$$u_p$$$.
4. $$$u_p$$$ is the root. This happens for only for one path, and clearly there must be a back edge from $$$u_1$$$ to $$$u_p$$$.
This is just what we wanted: doing just one DFS we can get one initial cycle and a series of paths we can use to successively augment our cycle until we have a hamiltonian cycle. One way to implement this is the following: first, we partition the graph into paths as in the previous theorem (we can mantain the representative back edge during the DFS; if a violation of the properties proven in the lemmas is detected, we halt). Then, we begin exploring the initial path (the one that forms a cycle with the root) in a downwards direction that is, first we visit $$$u_p$$$, then its child $$$u_{p-1}$$$, until we visit $$$u_1$$$, which has a edge back to $$$u_p$$$. When we visit one vertex, we push it into a vector that will contain the hamiltonian cycle at the end. If at some point we visit a vertex that is the parent of the endpoint of another path, we recursively visit that path and after visiting it we continue with our original path. But when recursively visiting the new path, we traverse it upwards, that is, we start with $$$u_1$$$ and go up to the parent of the vertex. If at some point we visit the endpoint of some other path, we again do a recursive visit of that path, this time in downwards direction. This way, we end up visiting all paths in a DFS-like way, and since we alternate between upward and downward traversals we end up having all the vertices of the graph in the vector ordered in a way that they form a hamiltonian cycle.
Now that we have found how to compute that hamiltonian cycle in linear time (or halt if we find that some of the necessary conditions for a good ordering are violated), let's see an additional necessary condition for a good ordering.
Theorem: In a (biconnected) graph $$$G$$$ with a good ordering, for any hamiltonian cycle, then there can not be any pair of edges that "cross", that is, if we draw the graph with vertices placed in a circle in the hamiltonian cycle order and with non-cycle edges drawn as chords, no two chords intersect.
Proof: Assume that two edges cross. We can label the vertices $$$v_1, \ldots, v_n$$$ so that $$$v_1, \ldots, v_n$$$ forms the hamiltonian cycle in that order, $$$v_{k} \leq_{v_{k+1}} v_{k+2}$$$ and the endpoints of the chords are $$$v_1, v_i$$$ and $$$v_p, v_q$$$, with $$$1 < p < i < q \leq n$$$. Consider the cycle $$$v_1, v_2, \ldots, v_p, v_q, v_{j+1}, \ldots$$$. Because of the orientation of the hamiltonian cycle (note that there are at least three consecutive vertices from the hamiltonian cycle in this cycle) we have that $$$v_{p-1} \leq_{v_p} v_q$$$. Similarly for the cycle $$$v_1, v_i, v_{i+1}, \ldots, v_n$$$, we see that $$$v_1 \leq_{v_i} v_{i+1}$$$. But now consider the cycle $$$v_1, v_i, v_{i+1}, \ldots, v_q, v_p, v_{p-1}, \ldots$$$. Because $$$v_1 \leq_{v_i} v_{i+1}$$$, we must also have $$$v_{q} \leq_{v_p} v_{p-1}$$$, contradiction. $$$\square$$$
Once we have found the hamiltonian cycle, this property can be checked in linear time. And now the properties we have checked are not only necessary but also sufficient:
Theorem: A biconnected graph $$$G$$$ with a hamiltonian cycle $$$v_1, \ldots, v_n$$$ such that non-cycle edges do not cross admits a good ordering.
Proof: We assign an ordering by choosing one orientation of the cycle, and ordering the edges of each vertex by how far is the endpoint of the edge traversing the cycle in that orientation. We have to prove that this is a good ordering. Let $$$v_{i_1}, v_{i_2}, \ldots, v_{i_c}$$$ be any cycle, and label the vertices $$$v_1, \ldots, v_n$$$ so that $$$i_1 = 1$$$ and $$$v_{i_1} \leq_{v_{i_2}} v_{i_3}$$$ according to the orientation. If we show that $$$i_1 < \ldots < i_c$$$, we will have shown that the cycle is consistent with the ordering. We already have $$$i_1 < i_2 < i_3$$$ by the labelling choice. Note that is $$$i_{k} < i_{k-1}$$$ is the first index to break the inequality, then if $$$1 < i_{k} < i_{k-2}$$$ the edge between $$$i_{k-1}$$$ and $$$i_k$$$ crosses some previous edge, and if $$$i_{k-2} < i_k$$$, then the cycle from then onwards be contained in the interval between vertices $$$v_{i_{k-2}}$$$ and $$$v_{i_{k-1}}$$$, which is not possible since vertex $$$v_1$$$ lies outside. $$$\square$$$
This ordering can be reconstructed in time $$$O(m \log m)$$$ by applying any standard sorting algorithm to the adjacency lists of the vertices (the comparison function is different for each vertex), and it can be improved to linear time by making an array of pairs consisting on the information of all the adjacency lists (each edge is included two times in the array, one for each end), sorting the array in linear time using counting sort, and then for each of the vertices the sorted adjacency list can be restored by applying one splice operation to the list given in the order in which the array was sorted.