Babysitting
Contest: Codeforces Round 912 (Div. 2)
Difficulty rating: 2500
Tags: 2-sat, binary search, data structures, graphs, trees

Theofanis wants to play video games, however he should also take care of his sister. Since Theofanis is a CS major, he found a way to do both. He will install some cameras in his house in order to make sure his sister is okay.

His house is an undirected graph with $$$n$$$ nodes and $$$m$$$ edges. His sister likes to play at the edges of the graph, so he has to install a camera to at least one endpoint of every edge of the graph. Theofanis wants to find a vertex cover that maximizes the minimum difference between indices of the chosen nodes.

More formally, let $$$a_1, a_2, \ldots, a_k$$$ be a vertex cover of the graph. Let the minimum difference between indices of the chosen nodes be the minimum $$$\lvert a_i - a_j \rvert$$$ (where $$$i \neq j$$$) out of the nodes that you chose. If $$$k = 1$$$ then we assume that the minimum difference between indices of the chosen nodes is $$$n$$$.

Can you find the maximum possible minimum difference between indices of the chosen nodes over all vertex covers?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^{5}, 1 \le m \le 2 \cdot 10^{5}$$$) — the number of nodes and the number of edges.

The $$$i$$$-th of the following $$$m$$$ lines in the test case contains two positive integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$), meaning that there exists an edge between them in the graph.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{5}$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^{5}$$$.

Output format:
For each test case, print the maximum minimum difference between indices of the chosen nodes over all vertex covers.

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

Note:
In the first test case, we can install cameras at nodes $$$1$$$, $$$3$$$, and $$$7$$$, so the answer is $$$2$$$.

In the second test case, we can install only one camera at node $$$1$$$, so the answer is $$$3$$$.

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

Example output:
2
3
2

Editorial:
We can solve this problem using 2-sat and binary search the answer.
In order to have a vertex cover we should have $$$(u_i | v_i)$$$.
And if we want to check if the answer is greater or equal to $$$mid$$$ we want to have $$$(!x | !y)$$$ for all pairs $$$1\le x, y \le n$$$ such that $$$|x - y| < mid$$$.
However, this way we will have too many edges.
To fix this problem we can create some helping nodes and edges in a similar structure of a segment tree.
In 2-sat when we connect two nodes there are two possibilities for each (taken or not taken). If we have an edge from $$$a$$$ to $$$b$$$ it means that when $$$a$$$ holds then definitely also $$$b$$$ holds.
So, we build a binary tree in a similar structure to a segment tree so that each node is connected to two children creating a binary-directed tree and each node corresponds to a range. When we want to have edges from $$$x$$$ to $$$[x+1,x+mid)$$$ and $$$(x-mid,x-1]$$$ we just choose the nodes in this binary tree that are needed to make the range (they are at most $$$\log(n)$$$).
So that makes the total time complexity to: $$$O(M \log^2(n))$$$
There is also an $$$O(M \log(n))$$$ solution. Shootout to jeroenodb for pointing it out.
The idea is similar.
We use 2-sat and binary search the answer, however, this time we do 2-sat differently.
In our graph, we will have the $$$m$$$ edges to have a vertex cover. So we should have $$$(u_i | v_i)$$$.
We add those edges and then we should also have the edges corresponding to $$$(!x | !y)$$$ for all pairs $$$1\le x, y \le n$$$ such that $$$|x - y| < mid$$$.
But we don't need all of them. We can just only go to first to the left and first to the right by storing the set of unvisited nodes and doing lower bound with dsu.