XXVI Olimpíada Brasileira de Informática
Dividindo o império
Um grande Império é composto por N cidades, numeradas de 1 até N. Alguns pares de cidades estão ligados diretamente por estradas bidirecionais e, por uma antiga tradição, esses pares são escolhidos de maneira que sempre é possível ir de qualquer cidade para qualquer outra cidade por exatamente um caminho (um caminho é uma sequência de estradas).
O imperador quer dividir seu império em dois para deixar de herança para seus dois filhos. Ele percebeu que basta destruir exatamente uma estrada, qualquer estrada, para dividir seu império em dois menores que, separadamente, preservam a antiga tradição. Ele agora precisa da sua ajuda para computar a menor diferença possível no número de cidades entre os dois impérios resultantes.
Entrada
A primeira linha da entrada contém um inteiro N, representando o número de cidades no império. As N-1 linhas seguintes contém, cada uma, dois inteiros A e B, indicando que existe uma estrada bidirecional ligando diretamente as cidades A e B.Saída
Seu programa deve imprimir uma linha contendo um inteiro representando a menor diferença possível no número de cidades entre os dois impérios resultantes.Restrições
- 2 ≤ N ≤ 105
- 1 ≤ A ≤ N, 1 ≤ B ≤ N
Informações sobre a pontuação
- Em um conjunto de casos de teste somando 40 pontos, N ≤ 10000
Exemplos
Entrada
4 1 2 2 3 3 4 |
Saída
0 |
Entrada
16 3 5 12 3 5 1 2 1 4 1 6 1 7 1 12 8 12 9 12 10 12 11 3 13 13 14 15 13 15 16 |
Saída
4 |
