Interfered-Jumped

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

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

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

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

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