DFS#11793
¡A todos les encantan las flores, pero las flores en los grafos son aún mejores!
Definamos el árbol DFS del grafo y la belleza del árbol.
\operatorname{DFS}_{\operatorname{path}}(G) — el árbol DFS del grafo (las aristas recorridas por DFS).
used = array de tamaño $|G|$ inicializado en $false$
edges = lista vacía
procedimiento DFS(nodo):
marcar $used_{nodo}$ como $true$
para cada vecino $v$ en $G_{nodo}$: # iterar sobre todas las aristas $(nodo, v)$ en el grafo original
si no $used_v$:
agregar $(nodo, v)$ a $edges$
DFS($v$)
procedimiento DFS_path(G):
DFS(1)
retornar $edges$La belleza del árbol se define de la siguiente manera: \operatorname{beauty}(T) = \sum_{i=1}^n \operatorname{deg}_i^2 donde \operatorname{deg}_i es el grado del vértice en el árbol .
Tu tarea es la siguiente: Construir un grafo simple conectado con vértices y aristas de tal manera que maximice \operatorname{beauty}(\operatorname{DFS}_{\operatorname{path}}(G)), donde es el grafo.
El problema tiene dos tipos de subtareas:
K = 1: Salida solo del valor máximo de \operatorname{beauty}(\operatorname{DFS}_{\operatorname{path}}(G)).
K = 2: Salida del valor máximo de \operatorname{beauty}(\operatorname{DFS}_{\operatorname{path}}(G)) y el grafo que alcanza este valor.
Un grafo es simple si cada arista conecta dos vértices distintos y no hay dos aristas que conecten el mismo par de vértices.
Un grafo es conectado si hay un camino entre cada par de vértices.
La línea contiene tres enteros , , (1 \leq n \leq 3 \cdot 10^5, n-1 \leq m \leq \min(3 \cdot 10^5, \frac{n \cdot (n-1)}{2}), 1 \leq K \leq 2) — número de vértices, número de aristas y tipo de subtarea.
En la primera línea, salida del valor máximo de \operatorname{beauty}(\operatorname{DFS}_{\operatorname{path}}(G)).
Si K = 2 entonces también salida de líneas, cada una conteniendo dos enteros , (1 \leq u, v \leq n), representando una arista en el grafo construido .
Nota que el orden en el que imprimes las aristas afecta el recorrido DFS y el valor de la función de belleza.
Ejemplo 1
Ejemplo 2
Ejemplo 3
En el tercer ejemplo, se podría construir el siguiente grafo:
Aquí los números en las aristas significan el orden de las aristas
Nuestro árbol DFS será:
La belleza de este es 1^2 + 2^2 + 3^2 + 1^2 + 1^2 = 16.
Se puede probar que es la mejor respuesta.
( puntos): n \leq 4, K = 1;
( puntos): n \leq 4, K = 2;
( puntos): n \leq 20, m \leq 20, K = 1;
( puntos): n \leq 20, m \leq 20, K = 2;
( puntos): n \leq 100, m \leq 100, K = 1;
( puntos): n \leq 100, m \leq 100, K = 2;
( puntos): K = 1;
( puntos): K = 2;