[중등부] 2023 KOI 2차대회 대비 모의고사 (3주차)

정올 마을에 N명의 주민이 살고 있다. 주민들은 각자 한 집에 한 명씩 살고 있으며, 집과 집을 연결하는 N-1개의 길이 존재한다.

모든 주민은 길을 통해서만 이동이 가능하고, 모든 주민은 다른 모든 주민들의 집에 방문 할 수 있다.

한 명의 주민을 기준으로 직접적으로 연결되어 있는 집에 거주하는 두 명의 주민을 포함한 총 세 명의 인접한 주민들은 삼총사가 될 자격이 있다.

N명의 주민들이 사는 마을에서 M쌍의 삼총사 후보들이 존재하는지 알아보자.