실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
수진은 건강을 위해 더 많이 운동해야 한다는 것을 깨달았습니다. 그녀는 아침 조깅 루틴에 사용할 수 있는 도시 주변의 잠재적인 경로를 선택하는 데 당신의 도움이 필요합니다.
도시에는 ()개의 블록이 있으며, 편리하게 1부터 까지 번호가 매겨져 있으며, 편리하게 개의 양방향 길()의 집합으로 편리하게 연결되어 있습니다.
사람들은 블록 간의 모든 이동에 대해 개의 길의 특정 부분 집합을 사용하는 경향이 있으며,. 이를 "포장" 길이라고 부릅니다. 포장 길만 사용하여 어떤 필드에서 다른 모든 필드로 이동할 수 있습니다.
아침 조깅을 재미있게 하기 위해, 수진은 비포장 길을 포함하는 루트를 선택해야 한다고 결정합니다. 그러나 포장 길을 사용하는 것이 너무 편안해서 그녀의 루트에서 비포장 길을 너무 많이 사용하고 싶지는 않습니다. 수진은, 시작점으로 돌아오는 간단한 사이클(시작점으로 돌아오며 어떤 블록도 두 번 이상 사용하지 않는)을 형성하는 좋은 루트는 정확히 두 개의 비포장 길을 포함하는 것이 좋다고 생각합니다.
수진이 사용할 수 있는 좋은 루트의 수를 계산하는 데 도움을 주세요. 두 루트는 동일한 길의 집합을 포함하는 경우 동일한 것으로 간주됩니다.
첫 번째 줄에는 과 이 주어집니다. 다음 개의 줄 각각에는 길의 끝점을 나타내는 두 정수 와 가 주어집니다. 이 중 처음 개는 포장 길입니다.
수진이 사용하고 싶어할 수 있는 총 루트의 수를 출력해야 합니다.
5 8 1 2 1 3 1 4 1 5 2 3 3 4 4 5 5 2
4
출처: USACO 2019 January Contest, Platinum Problem 2. Exercise Route