find the path with the greatest cost

The country of ALPHA has N cities and N – 1 two-way road connecting pairs of cities. HN's company won the bidding to repair 2 roads. A route is a sequence of different cities, linked by roads. The company is allowed to choose any 2 routes to fix, but they must choose 2 routes that do not intersect (i.e. there is not a city on both routes). that) Show that the profit of repairing each road is always equal to 1. The profit of repairing 2 routes is equal to the product of the profit of each route. HN's task is to find 2 routes to fix so that the maximum profit is obtained.

INPUT: TOWPATH.INP

• Line 1 contains the number N (2 <= N <= 200)

• The next N – 1 line each contains two integers u, v representing a road connection between u and v.

OUTPUT: TOWPATH.OUT

• The company's biggest profit

TOWPATH.INP

4

1 2

2 3

3 4

TOWPATH.OUT

1

TOWPATH.INP

4

1 2

1 3

1 4

TOWPATH.OUT

0

TOWPATH.INP

6

1 2

2 3

2 4

4 5

4 6

TOWPATH.OUT

4