사전순 최소 위상 정렬 최대화

수열 $a_1, a_2, \dots, a_n$이 1부터 $n$까지의 정수를 하나도 빠짐없이 한 번씩 담고 있으면 이 수열을 순열이라고 한다.

정점의 순열 $a_1, a_2, \dots, a_n$이 방향 그래프의 위상 정렬이라는 것은, $u$에서 $v$로 가는 모든 방향 간선에 대해 순열에서 $u$가 $v$보다 앞에 온다는 뜻이다.

$1 \le i < m$인 모든 $i$에서 $a_i = b_i$이고 $a_m < b_m$인 $m$이 존재하면, 순열 $a_1, a_2, \dots, a_n$은 순열 $b_1, b_2, \dots, b_n$보다 사전순으로 작다.

사이클이 없는 방향 그래프가 주어진다. 이 그래프에 방향 간선을 최대 $k$개까지 추가할 수 있고, 추가한 뒤에도 사이클이 없어야 한다. 이렇게 만든 그래프에서 사전순으로 가장 작은 위상 정렬을 $T$라고 하자. $T$가 사전순으로 가장 커지도록 추가할 간선을 고른다.

첫째 줄에 정수 $n$, $m$, $k$가 주어진다. 차례대로 정점 개수, 원래 그래프의 방향 간선 개수, 추가할 수 있는 방향 간선 개수이다 ($1 \le n \le 100\,000$, $0 \le m, k \le 100\,000$).

다음 $m$개 줄에는 정수 $u_i$, $v_i$가 주어지며, $u_i$에서 $v_i$로 가는 방향 간선을 뜻한다 ($1 \le u_i, v_i \le n$). 같은 간선이 여러 번 주어질 수 있다. 주어진 그래프에는 사이클이 없다.

첫째 줄에 위에서 정한 수열 $T$를 정수 $n$개로 출력한다. 수는 공백 하나로 구분한다.

둘째 줄에 정수 $x$를 출력한다. 그래프에 사이클이 없으면서 사전순으로 가장 작은 위상 정렬이 정확히 $T$가 되도록 만드는 데 추가해야 하는 방향 간선 개수의 최솟값이다. $x$는 항상 $k$ 이하이다.