給定$m$個二元組$(a,b)$，求兩個排列$p,q$，使得$\forall i\in[1,m]$，$(p_{a_i}-p_{b_i})(q_{a_i}-q_{b_i})>0$并最大化$\sum_i[p_i\neq q_i]$。 $n,m\leq 5\times 10^5$。

題目鏈接

---

\(Description\)
給定\(m\)個二元組\((a,b)\)，求兩個排列\(p,q\)，使得\(\forall i\in[1,m]\)，\((p_{a_i}-p_{b_i})(q_{a_i}-q_{b_i})>0\)并最大化\(\sum_i[p_i\neq q_i]\)。
\(n,m\leq 5\times 10^5\)。

\(Solution\)
把限制看成邊。題意可以化為：給一個無向圖，給邊定向，使存在兩個拓撲序且\(p_i=q_i\)的點盡量少。（感覺也很抽象，對我沒什么用）
考慮什么時候點\(x\)一定有\(p_x=q_x\)：和其它所有點相連的點肯定是。所以先將度數為\(n-1\)的點刪掉。
然后每個點至少和一個點沒有連邊。考慮一個點\(x\)和一個點集\(S\)（\(k=|S|\geq 1\)），滿足\(x\)與\(S\)中所有點無連邊（即\(x\)與\(S\)大小關系任意），那么取\(p_{x,S_1,S_2,...}=1,2,3,...,k,\ q_{x,S_1,S_2,...}=k,1,2,...,k-1\)顯然可以使\(x,S\)合法。
那如果能將圖劃分成若干個\((x,S)\)的結構，因為每個\((x,S)\)內部編號連續，\((x,S)\)之間的大小關系就不會改變，那么就找到解了。

那我們就模擬這個過程。稱上面的與\(S\)無連邊的\(x\)為關鍵點。
對于一個尚未考慮的\(x\)，任取與\(x\)無連邊的點記為\(y\)。

• 如果\(y\)也還沒考慮過（沒加入任何\((x,S)\)），那么將\(x,y\)劃分到一個結構中。
• 如果\(y\)在某個結構中，且是該結構的關鍵點 或 該結構大小為\(2\)，那么\(y\)仍作為關鍵點，將\(x\)加入該結構的\(S\)里。
• 如果\(y\)在某個結構中但不是該結構的關鍵點（有\(|(x,S)|>2\)），那么將\(y\)從該結構中刪掉，將\(x,y\)劃分到一個結構中。

可以發現這個構造只需滿足“對任意點存在一個和它沒有連邊的點”，且最終每個點都屬于一個結構且每個結構有一個關鍵點和\(|S|\geq 1\)。所以一定有解使所有\(i\)滿足\(p_i\neq q_i\)。

用set維護，復雜度\(O(n\log n)\)。或者unordered_map可以\(O(n)\)。（不過找一個與\(x\)無連邊的點需要sort一下與\(x\)相連的點，桶排太麻煩所以沒必要\(O(n)\)）

另一種做法（官方題解）：
考慮補圖，補圖里的邊即大小關系未定的點對。
只需考慮度數\(\leq n-2\)的點，它們在補圖中度數\(\geq 1\)，也即至少和一個點未確定大小關系。
考慮一個最小的能調整的結構：菊花圖（一個點\(x\)和一個集合\(S\)中所有點均有邊構成的菊花，\(|S|\geq 1\)）。調整方式同上。
所以題意變成：給一個圖，求一個邊集使得每個連通塊都是一個菊花圖。
那只需對每個連通塊求出任意一棵生成樹，DFS就可以且一定可以拆出若干菊花圖。然后在每個菊花上調整大小關系即可。
DFS是\(O(n)\)的。但第一種寫法好強啊。

---

//857ms	54100KB
#include <bits/stdc++.h>
#define pc putchar
#define gc() getchar()
#define pb emplace_back
typedef long long LL;
const int N=5e5+5;

int bel[N],pnt[N],P[N],Q[N];
std::set<int> st[N];
std::vector<int> e[N];

inline int read()
{
	int now=0,f=1; char c=gc();
	for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
	for(;isdigit(c);now=now*10+c-48,c=gc());
	return now*f;
}
void Solve()
{
	const int n=read(),m=read();
	for(int i=1,u,v; i<=m; ++i) u=read(),v=read(), e[u].pb(v), e[v].pb(u);
	for(int i=1; i<=n; ++i) std::sort(e[i].begin(),e[i].end());

	int tot=0,now=0;
	for(int x=1; x<=n; ++x)
		if(e[x].size()==n-1) P[x]=Q[x]=++now;
		else if(!bel[x])
		{
			int y=0; e[x].pb(N);
			for(auto v:e[x])
			{
				if(++y==x) ++y;
				if(y!=v) break;
			}
			int bely=bel[y];
			if(!bely)
				bel[x]=bel[y]=++tot, pnt[tot]=x, st[tot].insert(x), st[tot].insert(y);
			else if(pnt[bely]==y||st[bely].size()==2)
				pnt[bely]=y, bel[x]=bely, st[bely].insert(x);
			else
				st[bely].erase(y), bel[x]=bel[y]=++tot, pnt[tot]=x, st[tot].insert(x), st[tot].insert(y);
		}
	for(int i=1; i<=tot; ++i)
	{
		int p=pnt[i]; P[p]=++now;
		for(auto x:st[i])
			if(x!=p) Q[x]=now, P[x]=++now;
		Q[p]=now;
	}
	for(int i=1; i<=n; ++i) printf("%d ",P[i]); pc('\n');
	for(int i=1; i<=n; ++i) printf("%d ",Q[i]); pc('\n');

	for(int i=1; i<=n; ++i) bel[i]=0;
	for(int i=1; i<=tot; ++i) std::set<int>().swap(st[i]);
	for(int i=1; i<=n; ++i) std::vector<int>().swap(e[i]);
}

int main()
{
	for(int T=read(); T--; Solve());
	return 0;
}