You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

$B$ 国是一个拥有 $n$ 个城市的国家，$n$ 个城市依次编号为 $1, 2, \dots, n$。$B$ 国的首脑计划在国内修建 $m$ 条城市间的单向道路。

如果从一个城市 $x$ 出发，经过若干条道路能够到达城市 $y$，我们就称 $x$ 可达 $y$。特殊的，我们认为每个城市都可达它本身。注意：$x$ 可达 $y$ 并不一定意味着 $y$ 可达 $x$。

对于一个城市的集合 $S$，如果 $S$ 中任意两个城市 $u, v$ 都满足 $u$ 可达 $v$ 且 $v$ 可达 $u$，那么我们称 $S$ 是互通的。特殊的，大小为 $1$ 的集合总是互通的。

如果一个互通的城市集合 $A$ 满足不存在另一个互通的城市集合 $B$ 使得 $A$ 是 $B$ 的真子集，那么我们称 $A$ 是一个城市群。

可以证明，对于任意的修建 $m$ 条城市间的道路的方案，总能够将 $n$ 个城市划分为若干个城市群，满足每个城市恰好属于一个城市群且每个城市群包含至少一个城市。

$B$ 国的首脑要求这 $n$ 个城市恰好被划分成 $X$ 个城市群，他还有额外的 $q$ 个限制 $(a_i, b_i)$，要求城市 $a_i$ 与城市 $b_i$ 属于同一个城市群。

你需要构造一种修建 $m$ 条道路的方案满足首脑的要求，或者报告满足要求的方案不存在。

如果存在多种可能的方案，你可以输出任意一种。

注意：对于任意的两个城市 $u, v$，从 $u$ 到 $v$ 的道路只能修建至多一条；你不能修建从一个城市到它本身的道路。

输入格式

从标准输入读入数据。

第一行四个整数 $n, m, X, q$。

接下来 $q$ 行每行两个正整数，第 $i+1$ 行的两个正整数分别表示 $a_i, b_i$。

输出格式

如果不存在满足要求的方案，输出一行一个整数 $-1$。

否则输出 $m$ 行，每行两个正整数 $s_i, t_i$，表示你的方案中修建了一条从 $s_i$ 到 $t_i$ 的单向道路。

样例输入1

5 7 2 1
2 3

样例输出1

2 5
3 2
4 3
5 4
2 3
2 4
3 4

样例输入2

5 2 3 3
1 2
2 3
3 4

样例输出2

-1

数据范围

对于 $100\%$ 的数据，保证：

• $1 \le n, m \le 5 \times 10^5$
• $0 \le q \le 5 \times 10^5$
• $1 \le X, a_i, b_i \le n$
• $a_i \ne b_i$

具体数据范围如下表

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline void rd(T &x){
	x=0;char c=getchar();bool flag=false;
	while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	if(flag)x=-x;
}
template<typename T> inline void wr(T x){
	short st[30],tp=0;
	if(x<0) putchar('-'),x=-x;
	do st[++tp]=x%10,x/=10; while(x);
	while(tp) putchar('0'|st[tp--]);
}
#define kg putchar(' ')
#define dn putchar('\n')
#define R(i,l,r) for(int i=(l);i>=(r);--i)
#define F(i,l,r) for(int i=(l);i<=(r);++i)
//#define int long long
const int N=500005;
int n,m,u,v,x,q,fa[N],sz[N],nxt[N],U[N],V[N],tot;
vector<int>root;
vector<int>g[N];
int find(int i){return i==fa[i]?i:fa[i]=find(fa[i]);}
void merge(int i,int j){
	int fi=find(i),fj=find(j);
	if(fi!=fj)fa[fi]=fj,sz[fj]+=sz[fi];
}
void add(int i,int j){
	if(nxt[i]==j||i==j)return ;
	++tot,U[tot]=i,V[tot]=j;
}
bool cmp(int i,int j){return sz[i]<sz[j];}
void GG(){wr(-1),dn;exit(0);}
signed main(){
	rd(n),rd(m),rd(x),rd(q);
	F(i,1,n)fa[i]=i,sz[i]=1;
	F(i,1,q){rd(u),rd(v);merge(u,v);}
	F(i,1,n)if(fa[i]==i)root.push_back(i); 
	if(root.size()<x)GG();
	sort(root.begin(),root.end(),cmp);
	F(i,x,root.size()-1)fa[root[i]]=root[x-1];
	F(i,1,n)g[find(i)].push_back(i);
	F(i,1,n){
		int siz=g[i].size();
		if(siz<=1)continue;
		F(j,0,siz-1){
			add(g[i][j],g[i][(j+1)%siz]);
			nxt[g[i][j]]=g[i][(j+1)%siz];
		}
	}
	if(tot>m)GG();
	F(i,1,n){
		if(tot>=m)break;
		F(j,i+1,n){
			if(tot>=m)break;
			int fi=find(i),fj=find(j);
			if(fi<fj)add(i,j);
			else if(fi>fj)add(j,i);
			else add(i,j),add(j,i);
		}
	}
	if(tot<m)GG();
	F(i,1,m)wr(U[i]),kg,wr(V[i]),dn;
    return 0;
}