## Minimum Euler Cycle

So, we have a complete graph, where each edge needs to be visited only once and we need to find the lexicographical shortest such cycle.

It is a greedy problem, because we know we will start with the vertex 1 first. Then, we will look at shortest among its neighbours. We know it is 2, then we will stand at 2 and look for it’s shortest, we know it is 1. And repeat the process again and again.

To get a clear understanding of the approach, try to write down the adjacency list on paper:

Let us assume our n = 5.

1 -> 2,3,4,5

2->1,3,4,5

3> 1,2,4,5

4> 1,2,3,5

5> 1,2,3,4

Above is our adjacency list. We obviously are starting from node 1. Among it’s available neighbours, we see 2 is shortest, so we visit 2. Now, remove 2 from adjacency list of 1, because we know if we reach to vertex 1, we will not be able to visit 2 again, because we need to visit each edge only once. So updated list for vertex 1 is :

1 -> 3,4,5

Now, stand at 2 and we know we will visit 1. Repeat it again and again and we get this:

1 ->

2 -> 3,4,5

3-> 2,4,5

4-> 2,3,5

5 > 1,2,3,4

Notice that we cannot visit node 1 from vertex 5, because vertex 1 is not having any edge to visit, so it will be wrong. We, gonna visit node 2 here and repeat the entire process again.

We will notice, ultimately, only node 5 will be remaining with an edge to 1, rest all will be striked out. So, atlast, we again visit node 1.

Obviously, we cannot do this way implementation, as n is order 5. This will TLE. But, notice the final answer carefully.

It looks like this way:

1 -> (2,3,4,5) [First, 1 will come up with all this]

2 -> (3,4,5) [ Then, 2 will come with all this]

3 -> (4,5) [Then, 3 will come with all this]

4 -> (5) [Then, 4 will come with all this]

At last, always 1 will come.

Now, this becomes easy to implement. I have kept a counter, say ct, initialized to 1. If, ct=1, it means we are pairing 1 with [2.3.4.5] and there are exactly n-ct options available to pair with.

Using this, here is my code.

```void solve()
{
ll n,l,r;
cin >> n >> l >> r;
ll ct = 1;
bool flag=0;
if (r == (n*(n-1)+1)){
r--;
flag = 1;
}
while(l <= r){
if (l <= (n-ct)*2){
if (l%2 == 1){
cout << ct << " ";
l++;
}
else{
cout << ct + l/2 << " ";
l++;
}
}
else{
l -= 2*(n-ct);
r -= 2*(n-ct);
ct++;
}
}
if (flag){
cout << 1 << " ";
}
cout << endl;
}
```