从一般的求字典序最小的拓扑排序入手。考虑第一次加入无入度点后，得到了一个小根堆 $mn$ 。我们的目标是让这一次拿的是这个小根堆里面尽量大的数。先假装 $k$ 足够，于是我们把这里面除了最后一个数之外的所有数全部丢出小根堆并且维护到一个大根堆里面。然后对于最后一个数，如果它比大根堆的最大值还大，显然没有必要把它丢出去，直接用就是最优的。否则，肯定是把它也丢出去，然后拿大根堆里面的最大的出来，从拓扑序上上一次的点向这个点连边，这样一定能钦定在字典序最小的情况下，这个点的位置就在这里。

也就是说，当我们把一个数从小根堆拿到大根堆的时候，就意味着之后这个数出大根堆的时候一定会需要从拓扑序的最后一个位置向它连边，需要耗费 $1$ 的代价。

那么就有了一个做法。在小根堆直到只剩一个数前且 $k$ 足够时尽量 pop 并且丢进大根堆并更新 $k$ ，只剩一个的时候判断一下是否需要弹出。然后如果小根有东西就只能优先连小根堆的东西，且不需要加边，否则连大根堆的东西且用上次的点连向这个点。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m , k;
int A[MAXN];

vi G[MAXN];
priority_queue<int> Qmn , Qmx;
int deg[MAXN];

void solve() {
	cin >> n >> m >> k;
	rep( i , 1 , m ) {
		int u , v;
		scanf("%d%d",&u,&v);
		G[u].pb( v );
		++ deg[v];
	}
	rep( i , 1 , n ) if( !deg[i] ) Qmn.push( -i );
	vi as;
	int las = 0;
	vector<pii> ed;
	while( !Qmn.empty() || !Qmx.empty() ) {
		while( Qmn.size() && k && ( Qmn.size() > 1 || ( Qmx.size() && -Qmn.top() < Qmx.top() ) ) ) 
			Qmx.push( -Qmn.top() ) , Qmn.pop() , -- k;
		int u;
		if( Qmn.size() ) u = -Qmn.top() , Qmn.pop();
		else {
			u = Qmx.top() , Qmx.pop();
			ed.eb( mp( las , u ) );
		}
		as.pb( u );
		for( int v : G[u] ) {
			-- deg[v];
			if( !deg[v] ) Qmn.push( -v );
		}
		las = u;
	}
	for( int x : as ) printf("%d ",x); puts("");
	cout << ed.size() << endl;
	for( auto t : ed ) printf("%d %d\n",t.fi,t.se);
}

signed main() {
	freopen("graph.in" , "r" , stdin);
	freopen("graph.out" , "w" , stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}