TREECST - Tree Construction

Moles are tidy and hard-working animals. Our mole likes to keep its underground residence in utmost order, so that everyone living there knows where to find things.

To achieve this, the mole connected rooms with tunnels so that there is a single unique way to get from one room to any other room. The distance between two rooms is the number of halls passed on the way from one to the other.

Despite all the effort, some of the mole's guests are complaining that it takes too long to walk between certain pairs of rooms.

The mole decided to reconstruct her residence, closing one tunnel and opening a new one, so that the distance between the farthest two rooms is the smallest possible, but so that it is still possible to reach every room from every other room.

Write a program which determines the distance between the farthest two rooms after reconstruction, which tunnel to close and which to open.

Input

The first line contains an integer N (1 ≤ N ≤ 300 000), the number of rooms. The rooms are numbered 1 to N.

Each of the next N−1 lines contains two integers, the numbers of rooms a tunnel connects.

Output

Output on separate lines, in order:

  • The distance between the two farthest rooms after reconstruction.
  • A pair of integers representing a previously existing tunnel, which should be closed.
  • A pair of integers, the rooms between which a new tunnel should be opened.

Note: The solution will not necessarily be unique. Output any reconstruction plan which achieves the smallest distance between the farthest two rooms.

Example

Input
4
1 2
2 3
3 4

Output
2
3 4
4 2
Input
7
1 3
2 3
2 7
4 3
7 5
3 6

Output
3
2 3
7 3


Được gửi lên bởi:Jimmy
Ngày:2008-10-22
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ừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:COCI 2008-2009

hide comments
2019-07-10 16:15:28
thật ra tràn stack là do ngu chứ không phải do thiếu pragma
2018-07-02 18:29:47
ĐM stack T.T
UPD: bác nào tràn stack thì thêm dòng này vào đầu code nha :v
#pragma comment(linker, "/STACK: 2000000")

Last edit: 2018-07-02 18:47:27
2018-06-20 09:50:43
dfs thuong co lon ac
2018-06-20 09:29:32
thao khảo thuật toán và code : https://bit.ly/2K4I5Yc
2018-06-20 09:27:40
dfs thường rồi cout độ dài auto AC
2016-02-17 20:30:14
đm stack T.T
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.