#include<bits/stdc++.h>
using namespace std;
namespace IO
{
	char buff[1<<21],*p1=buff,*p2=buff;
	char getch(){return p1==p2&&(p2=((p1=buff)+fread(buff,1,1<<21,stdin)),p1==p2)?EOF:*p1++;}
	template<typename T>void read(T &x){char ch=getch();int fl=1;x=0;while(ch>'9'||ch<'0'){if(ch=='-')fl=-1;ch=getch();}while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getch();}x*=fl;}
	template<typename T>void read_s(T &x){char ch=getch();while(ch<'a'||ch>'z')ch=getch();while(ch>='a'&&ch<='z'){x+=ch;ch=getch();}}
	template<typename T,typename ...Args>void read(T &x,Args& ...args){read(x);read(args...);}
	char obuf[1<<21],*p3=obuf;
	void putch(char ch) {if(p3-obuf<(1<<21))*p3++=ch;else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=ch;}
	char ch[100];
	template<typename T>void write(T x) {if(!x)return putch('0');if(x<0)putch('-'),x*=-1;int top=0;while(x)ch[++top]=x%10+48,x/=10;while(top)putch(ch[top]),top--;}
	template<typename T,typename ...Args>void write(T x,Args ...args) {write(x);write(args...);}
	void put(string s){for(int i=0;i<s.size();i++)putch(s[i]);}
	void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}
using namespace IO;
struct Nene
{
	struct node
	{
		int nxt,to,id;
	}e[114514<<1];
	int head[114514],cnt_edge;
	void add_edge(int u,int v,int id)
	{
		e[++cnt_edge].to=v;
		e[cnt_edge].id=id;
		e[cnt_edge].nxt=head[u];
		head[u]=cnt_edge;
	}
}T,G;
int Case;
int n,m;
int a[114514];
namespace Tarjan
{
	int dfn[114514],low[114514],cnt;
	int stk[114514],top;
	int dcc[114514],cnt_dcc;
	vector<int>pdcc[114514];
	void init()
	{
		cnt=top=cnt_dcc=0;
		for(int i=0;i<=n;i++) dcc[i]=stk[i]=dfn[i]=low[i]=0,pdcc[i].clear();
	}
	void tarjan(int u,int fa)
	{
		int sum=0;
		dfn[u]=low[u]=++cnt;
		stk[++top]=u;
		for(int i=G.head[u];i;i=G.e[i].nxt)
		{
			int v=G.e[i].to;
			if(v==fa) ++sum;
			if(!dfn[v]) 
			{
				tarjan(v,u);
				low[u]=min(low[u],low[v]);
			}
			else if(v!=fa) low[u]=min(low[u],dfn[v]);
		}
		if(low[u]==dfn[u]&&sum<=1)
		{
			++cnt_dcc;
			while(stk[top+1]!=u)
			{
				dcc[stk[top]]=cnt_dcc;
				pdcc[cnt_dcc].push_back(stk[top]);
				--top;
			}
		}
	}
}
using Tarjan::dcc;using Tarjan::pdcc;using Tarjan::cnt_dcc;
struct Elaina
{
	int tot[114514],cnt[114514];
	int mx;
	void add(int x)
	{
		--tot[cnt[a[x]]];
		tot[++cnt[a[x]]]++;
		mx=max(mx,cnt[a[x]]);
	}
	void del(int x)
	{
		--tot[cnt[a[x]]];
		if(!tot[cnt[a[x]]]&&mx==cnt[a[x]]) --mx;
		tot[--cnt[a[x]]]++;
	}
}w[2];
int siz[114514],son[114514],dfn[114514],cnt_dfn,p[114514];
int ans[114514];
int id[114514];
int sum;
void dfs1(int u,int fa)
{
	siz[u]=1;dfn[u]=++cnt_dfn;p[cnt_dfn]=u;
	for(int i=0;i<pdcc[u].size();i++) w[0].add(pdcc[u][i]);
	for(int i=T.head[u];i;i=T.e[i].nxt)
	{
		int v=T.e[i].to;
		if(v==fa) continue;
		id[v]=T.e[i].id;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[son[u]]<siz[v]) son[u]=v;
	}
}
void dfs2(int u,int fa,int del,int val)
{
	for(int i=T.head[u];i;i=T.e[i].nxt)
	{
		int v=T.e[i].to;
		if(v==fa||v==son[u]) continue;
		dfs2(v,u,1,val);
	}
	if(son[u]) dfs2(son[u],u,0,val);
	for(int i=T.head[u];i;i=T.e[i].nxt)
	{
		int v=T.e[i].to;
		if(v==fa||v==son[u]) continue;
		for(int j=dfn[v];j<=dfn[v]+siz[v]-1;j++)
			for(int k=0;k<pdcc[p[j]].size();k++) w[1].add(pdcc[p[j]][k]),w[0].del(pdcc[p[j]][k]);
	}
	for(int i=0;i<pdcc[u].size();i++) w[1].add(pdcc[u][i]),w[0].del(pdcc[u][i]);
	ans[id[u]]=w[0].mx+w[1].mx-val;
	if(del) 
		for(int i=dfn[u];i<=dfn[u]+siz[u]-1;i++)
			for(int j=0;j<pdcc[p[i]].size();j++) w[1].del(pdcc[p[i]][j]),w[0].add(pdcc[p[i]][j]);
}
int cnmu[114514],cnmv[114514];
int main()
{
	read(Case);
	while(Case--)
	{
		read(n,m);
		Tarjan::init();
		cnt_dfn=T.cnt_edge=G.cnt_edge=0;
		for(int i=0;i<=n;i++) son[i]=dfn[i]=T.head[i]=G.head[i]=0;
		for(int i=1;i<=n;i++) read(a[i]);
		for(int i=1;i<=m;i++)
		{
			int u,v;
			read(u,v);
			cnmu[i]=u;cnmv[i]=v;
			if(u==v) continue;
			G.add_edge(u,v,i);G.add_edge(v,u,i);
		}
		for(int i=1;i<=n;i++) if(!Tarjan::dfn[i]) Tarjan::tarjan(i,0); 
		for(int i=1;i<=n;i++)
			for(int j=G.head[i];j;j=G.e[j].nxt)
			{
				int v=G.e[j].to;
				if(dcc[v]!=dcc[i]) T.add_edge(dcc[i],dcc[v],G.e[j].id);
			}
		sum=0;
		for(int i=1;i<=m;i++) ans[i]=0;
		for(int i=1;i<=cnt_dcc;i++)
		{
			if(dfn[i]) continue;
			dfs1(i,0);
			dfs2(i,0,1,w[0].mx);
			sum+=w[0].mx;
			for(int j=dfn[i];j<=dfn[i]+siz[i]-1;j++)
				for(int k=0;k<pdcc[p[j]].size();k++)
					w[0].cnt[a[pdcc[p[j]][k]]]=w[1].cnt[a[pdcc[p[j]][k]]]=0;
			for(int j=0;j<=w[0].mx;j++) w[0].tot[j]=w[1].tot[j]=0;
			w[0].mx=w[1].mx=0;
		}
		if(m==2&&ans[1]+sum==7&&ans[2]+sum==7)
		{
			cout<<n<<" "<<m<<endl;
			for(int i=1;i<=n;i++) cout<<a[i]<<" ";
			cout<<endl;
			for(int i=1;i<=m;i++) cout<<cnmu[i]<<" "<<cnmv[i]<<endl;
		}
//		for(int i=1;i<=m;i++) 
//		{
//			write(sum+ans[i]);
//			if(i<m) putch(' ');
//		}
//		putch('\n');
	}
	flush();
}
/*
1
2 7
79960 79960
2 2
1 1
1 1
2 2
1 1
2 1
1 2
*/