#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Přednačtená, nezpracovaná polovina hrany
struct edge_raw {
  unsigned vertex, index;
};

// Jeden vrchol
struct vertex {
  // První hrana tohoto vrcholu. Další následují za ní, až do první hrany následujícího vrcholu
  unsigned edges;
  // Spočítané nejdelší cesty
  struct longest {
    // Nejdelší vedoucí tudy, nejdelší celková
    unsigned local, subtree;
    // Vrchol, kterým prochází nejdelší cesta v tomto podgrafu
    unsigned vertex;
    // Sousedi v cestě, která prochází tudy
    unsigned neighbors[2];
  } longest[2];
};

// Počet vrcholů
static unsigned tree_size;
// Přednačtené hrany
static struct edge_raw (*edges_raw)[2];
// Graf
static struct vertex *vertices;
static unsigned *edges;

// Najde nejdelší cestu v podstromu s kořenem index a nevrací se do parent
// Výsledky ukládá do longest[result]
static void path_search(unsigned index, unsigned parent, unsigned result) {
  // Případ, kdy nic hezkého nebylo nalezeno
  unsigned longest_subtree = 0, subtree_vertex = index;
  unsigned longest_neigh[3];
  unsigned local_lengths[3] = {};
  // Hrany vedoucí ze mě
  for(unsigned i = vertices[index].edges; i < vertices[index + 1].edges; i ++) {
    unsigned vertex = edges[i];
    if(vertex == parent) // Odsuď jsem přišel
      continue;
    if(vertex == tree_size) // Tahle hrana tu není (je "vypnutá")
      continue;
    // Prohledat tento podstrom
    path_search(vertex, index, result);
    // Je to zajímavé? Je tam něco dostatečně dlouhého?
    if(vertices[vertex].longest[result].subtree > longest_subtree) {
      subtree_vertex = vertices[vertex].longest[result].vertex;
      longest_subtree = vertices[vertex].longest[result].subtree;
    }
    for(int j = 1; j >= 0; j --)
      if(vertices[vertex].longest[result].local + 1 >= local_lengths[j]) {
        longest_neigh[j + 1] = longest_neigh[j];
        local_lengths[j + 1] = local_lengths[j];
        longest_neigh[j] = vertex;
        local_lengths[j] = vertices[vertex].longest[result].local + 1;
      }
  }
  // Vyplnit sebe z toho, co se spočítalo
  memcpy(vertices[index].longest[result].neighbors, longest_neigh, 2 * sizeof *longest_neigh);
  vertices[index].longest[result].local = local_lengths[0];
  // Nejdelší prochází skrz mě
  if(local_lengths[0] + local_lengths[1] > longest_subtree) {
    vertices[index].longest[result].subtree = local_lengths[0] + local_lengths[1];
    vertices[index].longest[result].vertex = index;
  } else { // Nejdelší v některém podstromu
    vertices[index].longest[result].subtree = longest_subtree;
    vertices[index].longest[result].vertex = subtree_vertex;
  }
}

// Vytáhne nejdelší cestu v subtree z grafu do output
static void path_fill(unsigned subtree, unsigned result, unsigned *output) {
  // Najdi nejvyšší vrchol na cestě
  unsigned vertex = vertices[subtree].longest[result].vertex;
  unsigned length = vertices[subtree].longest[result].subtree;
  unsigned index = vertices[vertex].longest[result].local;
  // Umísti ho na správné místo
  output[index] = vertex;
  // Projdi oba konce cesty odsud
  for(unsigned i = 0, pos = vertices[vertex].longest[result].neighbors[0]; i < index;
		  i ++, pos = vertices[pos].longest[result].neighbors[0])
    output[index - 1 - i] = pos;
  for(unsigned i = index + 1, pos = vertices[vertex].longest[result].neighbors[1]; i <= length;
		  i ++, pos = vertices[vertex].longest[result].neighbors[0])
    output[i] = pos;
}

int main(int argc, char *argv[]) {
  // Jen otravné načítání souboru
  FILE *f = fopen("optstro.in", "rt");
  fscanf(f, "%zu", &tree_size);
  if(tree_size < 2)
  {
    fprintf(stderr, "Nemá hrany, nelze optimalizovat\n");
    return EXIT_FAILURE;
  }
  // Jeden navíc - zarážka
  vertices = malloc((tree_size + 1) * sizeof *vertices);
  for(unsigned i = 0; i < tree_size; i ++)
    vertices[i].edges = 0;
  // O jednu hranu méně než vrcholů
  edges_raw = malloc((tree_size - 1) * sizeof *edges_raw);
  // Načíst hrany, spočítat, kolik patří kterému vrcholu
  for(unsigned i = 0; i < tree_size - 1; i ++)
    // Každá hrana má 2 konce, uložme si je
    for(unsigned j = 0; j < 2; j ++) {
      fscanf(f, "%zu", &edges_raw[i][j].vertex);
      edges_raw[i][j].vertex --; // Soubor je od 1, v programu indexujeme od 1 od 0
      edges_raw[i][j].index = vertices[edges_raw[i][j].vertex].edges ++;
    }
  fclose(f);
  // Zařadit hrany, kam patří, připravit vrcholy
  unsigned current_pos = 0;
  for(unsigned i = 0; i <= tree_size; i ++) {
    unsigned size = vertices[i].edges;
    vertices[i].edges = current_pos;
    current_pos += size;
  }
  // Každá hrana je tu 2* - jednou tam, jednou zpět
  edges = malloc((tree_size - 1) * 2 * sizeof *edges);
  for(unsigned i = 0; i < tree_size - 1; i ++)
    for(unsigned j = 0; j < 2; j ++)
      edges[vertices[edges_raw[i][j].vertex].edges + edges_raw[i][j].index] = edges_raw[i][1 - j].vertex;
  // Neroztříděné hrany už nejsou potřeba
  free(edges_raw);

  // Teď to zajímavé. Najdeme si nejdelší cestu.
  // Zavolat rekurzivní fci. zakořeněnou v 0. vrcholu a s neexistujícím rodičem
  path_search(0, tree_size, 0);
  // Vyplnit cestu
  unsigned path_len = vertices[0].longest[0].subtree;
  unsigned *path = malloc((path_len + 1) * sizeof *path);
  path_fill(0, 0, path);
  // Co jsou konce cesty? Budeme z nich znovu hledat.
  unsigned a = path[0], b = path[path_len];
  // Spočítat velikosti cest ve zbylých stromech
  path_search(a, tree_size, 0);
  path_search(b, tree_size, 1);
  // Která hrana je ta nejlepší?
  unsigned best;
  unsigned best_val = tree_size + 1; // Něco dostatečně velkého
  for(unsigned i = 0; i < path_len; i ++)
  {
    unsigned left = vertices[path[i]].longest[1].subtree;
    unsigned right = vertices[path[i + 1]].longest[0].subtree;
    unsigned trough = (left + 1) / 2 + (right + 1) / 2 + 1;
    unsigned total = (left > right) ? left : right;
    total = (total > trough) ? total : trough;
    // Tahle hrana je lepší
    if(total < best_val)
    {
      best_val = total;
      best = i;
    }
  }

  // Načíst nejlepší hranu
  unsigned e[] = { path[best], path[best + 1] };
  free(path); // Zbytek cesty není potřeba
  printf("Odebrat: %zu-%zu\n", e[0] + 1, e[1] + 1);
  // Použít už spočítané cesty k nalezení středů, spojit
  for(unsigned i = 0; i < 2; i ++) {
    unsigned path_len_short = vertices[e[i]].longest[1 - i].subtree;
    unsigned *path_short = malloc((path_len_short + 1) * sizeof *path_short);
    // Zkopírovat cestu (nebyla by potřeba celá, ale takto je to méně práce a může se hodit při ladění)
    path_fill(e[i], 1 - i, path_short);
    // Načíst novou, optimálnější hranu
    e[i] = path_short[path_len_short / 2];
    free(path_short);
  }
  printf("Přidat: %zu-%zu\n", e[0] + 1, e[1] + 1);
  // Zrušit graf
  free(edges);
  free(vertices);
  return EXIT_SUCCESS;
}