1352G - Special Permutation - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1001;
vector<int> v[N + 1];
vector<bool> d(N + 1);
int n;
void reset()
{
    for(int i = 1; i <= n; i++)
    {
        v[i].clear();
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 2; j <= 4; j++)
        {
            if(i + j <= n)
                v[i].push_back(i + j);
            if(i - j >= 1)
                v[i].push_back(i - j);
        }
    }
}

vector<int> ans(N + 1);
bool ok;

void dfs(int u, int num)
{
    if(ok) return;
    ans[num] = u;
    if(num == n)
    {
        ok = true;
        for(int i = 1; i <= n; i++)
            cout << ans[i] << ' ';
        return;
    }
    for(int x : v[u])
    {
        if(d[x]) continue;
        d[x] = true;
        dfs(x, num + 1);
    }
}

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        if(n <= 3) {
            cout << -1 << '\n';
            continue;
        }
        reset();
        for(int i = 1; i <= n; i++)
        {
            ok = false;
            for(int j = 1; j <= n; j++)
                d[j] = false;
            d[i] = true;
            ans[1] = i;
            dfs(i, 1);
            if(ok) break;
        }
        cout << '\n';
    }
	return 0;
}