시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 76 | 29 | 20 | 38.462% |
어느 행성에 N개의 작은 부족들이 살고 있다. 편의상 1부터 N까지 번호를 부여하자.
이 때, N개의 부족 내의 서로 다른 "삼자 동맹 관계"와 "삼자 적대 관계"들을 전부 합한 개수를 구하라.
예를 들어 N = 5이고 부족1-부족2, 부족1-부족3, 부족4-부족5가 서로 동맹 관계, 나머지 부족 쌍은 모두 적대 관계라고 가정하자. 이 경우 (2, 3, 4)와 (2, 3, 5) 가 "삼자 적대 관계"를 만족하고, "삼자 동맹 관계"는 없기 때문에 답은 2가 된다.
다른 예로 N = 5이고 부족1-부족2, 부족2-부족3, 부족1-부족3이 동맹인 경우 (1, 2, 3)은 "삼자 동맹 관계"이고, (1, 4, 5), (2, 4, 5), (3, 4, 5)는 "삼자 적대 관계"이기 때문에 답은 4가 된다.
첫 줄에 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 10).
각 테스트 케이스 첫 줄에 N, M이 공백으로 구분 되어 주어진다.
다음 M줄에 걸쳐서 한 줄에 두 개의 정수 x, y가 주어지는데 이는 x와 y가 동맹임을 나타낸다.
입력으로 주어지는 동맹 관계는 언제나 1 ≤ x < y ≤ N을 만족하고, 같은 부족 쌍이 여러 번 주어지는 경우는 없다.
입력으로 주어지지 않은 부족 쌍은 적대관계라고 가정한다.
각 테스트 케이스에 대해 한 줄에 동맹-반동맹 계수를 출력한다.
3 3 1 1 2 5 3 1 2 2 3 1 3 5 3 1 2 1 3 4 5
0 4 2