#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5;
int vs[nx], rt, pa[nx], deg[nx], h[nx];
vector<int> d[nx], res;
priority_queue<pair<int, int>> pql, pqr;
void dfs(int u)
{
if (!vs[pa[u]]&&pa[u]!=rt) deg[pa[u]]++;
for (auto v:d[u]) if (!vs[v]) h[v]=h[u]+1, dfs(v);
}
void dfsfill(int u, priority_queue<pair<int, int>> &pq)
{
if (deg[u]==0) pq.push({h[u], u});
for (auto v:d[u]) if (!vs[v]) dfsfill(v, pq);
}
std::vector<int> createFunTour(int N, int Q) {
for (int i=1; i<N; i++) d[(i-1)/2].push_back(i), pa[i]=(i-1)/2;
rt=0;
while (1)
{
int cnt=0;
//cout<<"root "<<rt<<'\n';
for (auto x:d[rt]) if (!vs[x]) cnt++;
if (cnt==0)
{
res.push_back(rt);
vs[rt]=1;
break;
}
if (cnt==1)
{
res.push_back(rt);
vs[rt]=1;
for (auto x:d[rt])
{
if (!vs[x]);
rt=x;
break;
}
continue;
}
if (cnt==2)
{
for (int i=0; i<N; i++) deg[i]=0;
while (!pql.empty()) pql.pop();
while (!pqr.empty()) pqr.pop();
dfs(d[rt][0]);
dfsfill(d[rt][0], pql);
dfs(d[rt][1]);
dfsfill(d[rt][1], pqr);
if (pql.top().first<pqr.top().first) swap(pql, pqr);
while (!pql.empty())
{
auto [_, u]=pql.top();
pql.pop();
res.push_back(u);
vs[u]=1;
if (pa[u]!=rt) --deg[pa[u]];
if (pa[u]!=rt&°[pa[u]]==0) pql.push({h[pa[u]], pa[u]});
swap(pql, pqr);
}
res.push_back(rt);
vs[rt]=1;
int nrt=-1;
cnt=0;
for (auto x:d[rt]) if (!vs[x]) nrt=x;
if (nrt==-1) break;
rt=nrt;
}
}
/*
cout<<"res : ";
for (auto x:res) cout<<x<<' ';
cout<<'\n';
*/
return res;
}
