시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 57 6 6 14.286%

문제

넓은 강이 있는 나라가 있다. 강의 왼쪽에는 마을이 N개, 오른쪽에도 N개가 있으며, 각 마을은 1번부터 N번까지 번호가 매겨져 있다. 왼쪽 마을 중 하나와 오른쪽 마을 중 하나를 연결하는 배는 총 M개가 있고, 양방향으로 연결한다.

상근이는 총 4개 마을에서 영화제를 개최하려고 한다. 왼쪽 마을에서 2개, 오른쪽 마을에서 2개를 고르며, 왼쪽 마을은 모두 오른쪽 마을과 배로 직접 연결되어 있어야 한다.

영화제를 개최할 마을을 고르는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 마을의 수 N (2 ≤ N ≤ 1000)과 배의 수 M (4 ≤ M ≤ N2)이 주어진다.

다음 M개 줄에는 배가 연결하는 두 마을의 번호가 왼쪽, 오른쪽 순서대로 주어진다.

출력

영화제를 개최할 마을을 고르는 방법의 수를 출력한다.

예제 입력

3 7
1 1
1 3
2 1
2 3
3 1
3 2
3 3

예제 출력

3

힌트