시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)105272027.027%

문제

Runo NFT는 AI Network에 흥미가 있는 사람들이 간편하게 생태계에 참여할 수 있도록 하기 위해 만들어진 AINFT이다. 사람들은 Runo NFT를 구입하는 것만으로 AI Network의 노드 운영에 참여하고 보상을 얻을 수 있다.

Runo NFT의 마스코트 캐릭터는 달리기를 좋아하는 루노(Runo)이다. 루노는 달리면 달릴수록 성장하고, 성장할수록 다양한 아이템을 얻어서 착용할 수 있게 된다.

아이템은 모자, 신발, 날개, 배경의 네 가지 속성이 있으며, 루노는 각 속성의 아이템을 최대 하나씩 착용할 수 있다. 지금은 네 속성 각각에 $N$종류의 아이템이 있어서, $1$에서 $N$사이의 번호로 다른 아이템을 구분한다.

루노의 디자이너 아인(AIN)이는 여러 아이템을 루노에게 착용시켜보며 외형이 어떤 식으로 조합되는지 테스트하고 있다. 그러다 보니, 같이 착용하는 것이 미관상 좋지 않은 아이템들이 있다는 것을 알게 되었다.

그렇게 아인이는 서로 어울리지 않는 두 아이템의 쌍 $M$개를 정리했고, 이들은 서로 같이 착용하는 것을 막으려고 한다.

이때 네 가지 속성의 아이템을 모두 착용한 루노가 가질 수 있는 서로 다른 외형은 총 몇 가지일까?

입력

첫 번째 줄에 각 속성별 아이템의 개수 $N$과 서로 같이 착용하려는 것을 막으려는 두 아이템 쌍의 개수 $M$이 주어진다.

다음 $M$개의 줄에 서로 같이 착용해서는 안 되는 두 아이템 쌍이 주어진다. 각 줄에는 네 정수 $p, x, q, y$가 주어지며, 이는 $p$ 속성의 $x$번 아이템과 $q$ 속성의 $y$번 아이템을 같이 착용해서는 안 된다는 뜻이다. 여기서 $p$와 $q$는 편의를 위해 각 속성을 정수로 나타낸 것으로, $1$은 모자, $2$는 신발, $3$은 날개, $4$는 배경을 의미한다.

출력

첫 번째 줄에 네 가지 속성의 아이템을 모두 착용한 루노가 가질 수 있는 서로 다른 외형이 총 몇 가지인지 출력하라.

제한

  • $1 \leq N \leq 3\,000$
  • $0 \leq M \leq 10\,000$
  • $1 \leq p < q \leq 4$
  • $1 \leq x, y \leq N$
  • 같은 쌍이 여러 번 등장하지 않는다.

예제 입력 1

3 1
1 1 2 1

예제 출력 1

72

예제 입력 2

3 2
1 1 2 1
3 1 4 1

예제 출력 2

64

예제 입력 3

3 3
1 1 2 1
3 1 4 1
2 1 3 1

예제 출력 3

60

예제 입력 4

3 4
1 1 2 1
3 1 4 1
2 1 3 1
1 1 4 1

예제 출력 4

56

출처

Contest > AI Network Scholarium > AI Network Scholarium I C번