Grafo#7618
Una secuencia a_1, a_2, \ldots, a_n se llama permutación si contiene cada número entero desde hasta exactamente una vez.
Una permutación de los vértices a_1, a_2, \ldots, a_n se llama ordenación topológica de un grafo dirigido si para cada arista dirigida de a , el vértice aparece antes que el vértice en esta permutación.
Una permutación a_1, a_2, \ldots, a_n es lexicográficamente menor que una permutación b_1, b_2, \ldots, b_n si existe un índice tal que a_i = b_i para todo 1 \le i < m y a_m < b_m.
Se da un grafo dirigido acíclico. Añada a él como máximo aristas dirigidas de modo que el grafo resultante siga siendo acíclico y su ordenación topológica lexicográficamente menor sea lo más grande posible.
La primera línea contiene tres números enteros , y k~(1 \le n \le 10^5, 0 \le m, k \le 10^5) — la cantidad de vértices y aristas dirigidas en el grafo original, así como la cantidad máxima de aristas dirigidas que se permite añadir.
Cada una de las siguientes líneas contiene dos números enteros u_i y v_i~(1 \le u_i, v_i \le n), que describen una arista dirigida de u_i a v_i.
Se garantiza que el grafo no contiene ciclos.
En la primera línea, escriba números enteros — la ordenación topológica lexicográficamente menor del grafo modificado. En la segunda línea, escriba un número entero (0 \le x \le k) — la cantidad de aristas dirigidas añadidas. En cada una de las siguientes líneas, escriba la descripción de una arista añadida en el mismo formato que en los datos de entrada.
Ejemplo 1
Ejemplo 2