最近一段时间有点忙，先就补一道，剩余的以后再补啦

H.小鸡的排列构造

题干：给定组约束，构造一个长度的排列，满足对于每对约束，区间内的元素从小到大排序后，位于处的元素位置将会改变。特别地，对于每组测试，保证的奇偶性相同（？）

最后这句话赛时其实挺疑惑的，实在是想不出奇偶性与这题有什么联系。不过，可以肯定的是，奇偶性与该题的构造方法必定强相关，即区间长度全为奇数是一种构造，全为偶数则又是一种构造。

那么怎么构造这样的序列出来呢？如果一个个区间考虑，那这些区间的重叠等情况将会很不好处理，所以我们干脆直接将约束加到最强：

如果所有区间长度为偶数，则我们直接约束所有长度为的区间，必须保证这些区间中，每个元素排序后改变位置。显然，此时只需要倒序输出到，即为正确的答案。

如果为奇数呢？同理，由于，因此我们直接约束所有长度为的区间。如果只考虑一个长度为的区间，合法的构造也只有和了（注意：这里的只是用来表示相对大小，而不是真正的值）。那现在把两个区间拼到一块，就可以得到，在保证所有数都不同的情况下，可以构造出（同样地，这里的数只表示相对大小）。

至于那堆区间限制？其实除了提供奇偶性的判断外，就没什么用了（

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII array<int, 2>

const int inf = 4e18;
const int N = 1e6 + 5;
int t = 1, n, m;
int arr[N];

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        int tt = 0;
        while (m--)
        {
            int l, r,c;
            cin >> l >> r>>c;
            tt = (r - l + 1) % 2;
        }
        if (tt==0)
        {
            for (int i = n; i >= 1; i--)
                cout << i << ' ';
        }
        else
        {
            for (int i = n; i >= 2; i -= 2)
            {
                cout << i - 1 << ' ' << i << ' ';
            }
            if(n%2==1)
                cout << 1;
        }
        cout << '\n';
    }
    return 0;
}