사신도 ¶

• * 사신도(http://www.algospot.com/judge/problem/read/FOURGODS)
  
• A-B-C-D(-A) 와 같은 순서가 되도록 하는 것의 경우의 수 구하기
  
  • 염주 수열은 같은 것으로 본다.
    
• 모든 A와 C에 대해서 한다.(n^2)
  
  • B와 D의 후보를 찾아서 조건에 맞는지 확인한다.(A,C와 연결되어있는지) (n)
    
  • 토탈 n^3
    
• 중복제거. A-B-C-D는 숫자로 주어지므로 우선순위를 정한다.(e.g. 작은 숫자 우선)
  
  • A가 항상 가장 작은 숫자가 되도록 한다. B와 C의 크기는 바뀔 수 있는데, A-B-C-D와 A-C-B-D 둘 모두 다른 정답으로 보기 때문이다.
    

//
//  fourgods.cpp
//  codersHigh2013
//
//  Created by Jereneal Kim on 13. 8. 6..
//  Copyright (c) 2013년 Jereneal Kim. All rights reserved.
//

#include <iostream>
using namespace std;
int T,N,M;
int arr[501][501];
typedef struct Edge{
	int u;
	int v;
}Edge;
bool comp(Edge a,Edge b){
	if(a.u!=b.u){
		return a.u<b.u;
	}else{
		return a.v<b.v;
	}
}


int main(int argc, const char * argv[])
{
	freopen("/Users/jkim/Development/C&C++/codersHigh2013/codersHigh2013/input.txt","r",stdin);
	int i,j,k,num;
	scanf("%d",&T);
	for(int iter=0;iter<T;iter++){
		num=0;
		for(i=0;i<500;i++){
			for(j=0;j<500;j++){
				arr[i][j] = 0;
			}
		}//initalize
		
		scanf("%d %d",&N,&M);
		for(i=0;i<M;i++){
			int tmp1,tmp2;
			scanf("%d %d",&tmp1,&tmp2);
			arr[tmp2][tmp1] = 1;
			arr[tmp1][tmp2] = 1;
		}
		// get A & C
		for(i=1;i<=N;i++){
			for(k=i+1;k<=N;k++){
				int tmpNum=0;
				for(j=i+1;j<=N;j++){
					if(arr[i][j]&&arr[j][k]){
						tmpNum++;
					}
				}
				num+=tmpNum*(tmpNum-1)/2;
				num%=20130728;
			}
		}

		printf("%d\n",num);
	}
    return 0;
}