Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TRIPHP - Chuyến đi ngắn nhất

Làng của Buba là nơi nổi tiếng với nhiều danh lam thắng cảnh, thu hút hàng nghìn khách du lịch từ nhiều nơi trên thế giới. Làng có  địa điểm du lịch (đánh số từ 1 đến ) và  con đường độ dài 1 nối các cặp địa điểm. Hai địa điểm bất kì đều có thể đi đến nhau qua các con đường này.

Có khách du lịch tại địa điểm 1, những người khách được đánh số từ 1 tới . Người khách thứ nhất muốn thăm tất cả các địa điểm, người khách thứ hai muốn thăm tất cả các địa điểm chia hết cho 2, người khách thứ ba muốn thăm tất cả các địa điểm chia hết cho 3, … Cụ thể là người khách thứ  muốn thăm tất cả các địa điểm chia hết cho .

Yêu cầu: Công ty du lịch muốn lập hành trình cho từng du khách bắt đầu từ địa điểm 1 đi thăm các địa điểm khác rồi quay trở về địa điểm 1 sao cho mỗi du khách được đi qua tất cả các địa điểm anh ta muốn thăm (hành trình có thể qua những địa điểm khác nữa). Bạn cần cho biết độ dài hành trình ngắn nhất của mỗi du khách thỏa mãn yêu cầu trên.

Ví dụ

 

Giải thích về hành trình vài du khách

Du khách 1 đi theo hành trình  

Du khách 2 và 4 đi theo hành trình

Ít nhất 40% số điểm ứng với các test có N <= 100

Input

  • Dòng 1: Chứa số nguyên dương N <= 10^5.
  • N dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v cách nhau ít nhất một dấu cách mô tả một con đường nối địa điểm  tới địa điểm .

Output

Ghi ra file văn bản   dòng, dòng thứ  ghi một số nguyên duy nhất là độ dài quãng đường ngắn nhất mà du khách thứ phải đi

Example

Input:

5

1 2

1 3

4 2

5 2

Output:

8

4

2

4

4


Được gửi lên bởi:VOJ Team
Ngày:2012-12-24
Thời gian chạy:3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2016-12-22 17:30:58
tk cmt dưới vo hox thật
2015-12-29 10:33:01 minhsn
trau cung ac

Last edit: 2017-10-03 18:22:49
2014-12-11 14:08:17 Kraken
3 ngày dài mới ac được :((
2012-12-26 21:09:38 dhkhtn
sao bi loi thieu chu the nhi?
2012-12-25 03:51:50 King siêu kul
n - 1 dòng tiếp theo chứ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.