Interfered-Jumped

FXC 나라 국가대표 코치 희승이는 육상선수 제이의 훈련을 위해 아브레 선수촌에 도착하였다. 아브레 선수촌은 $N$개의 구역을 $N-1$개의 양방향 도로로 이어서 모든 구역을 직접 또는 간접적으로 연결하고 있다. 모든 구역에는 $0$ 이상 $N-1$ 이하의 서로 다른 정수 번호가 붙어 있다.

희승이는 육상 연습을 위해 선수촌의 일부 구역에 허들을 설치하려 한다. 허들이 너무 빽빽하게 배치되어 있으면 제이의 연습 효율이 떨어지므로, 도로로 직접 연결된 두 구역에는 동시에 허들을 배치할 수 없다.

희승이는 허들을 미리 설치한 다음 가능한 모든 종류의 연습 코스를 만든다. 연습 코스는 다음 조건을 만족해야 한다.

• 연습 코스는 $2$개 이상의 구역을 포함하는 경로이다.
• 같은 구역을 두 번 이상 지날 수 없다.
• 연습 코스는 최대한 많은 구역을 지나야 한다.

희승이는 제이가 선수촌을 둘러보면서 하나 이상의 연습 코스에 포함되는 구역이 몇 개인지 파악할 수 있으면 좋겠다고 한다. 그러나 제이는 선수촌 지도가 없으므로, 각 구역마다 자신과 인접한 구역에 있는 허들의 수를 센 다음 답을 예측해야 한다. 희승이가 허들을 배치하고 제이가 답을 예측하는 방법을 구현하는 프로그램을 작성하여라.