시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 25 12 7 100.000%

문제

어느 행성에 N개의 작은 부족들이 살고 있다. 편의상 1부터 N까지 번호를 부여하자.

  • 임의의 서로 다른 두 부족은 서로 동맹 관계이거나 서로 적대 관계이다. 이 관계는 대칭적이다. 즉, 부족 A는 부족 B를 동맹이라 생각하나 B는 A를 적이라 생각하는 경우는 없다.
  • 부족 A와 부족 B가 동맹이고, 부족 B와 부족 C가 동맹이라도 부족 A와 부족 C가 적대 관계일 수 있다.
  • 임의의 서로 다른 세 부족에 대하여, 세 부족이 서로 동맹 관계인 경우를 "삼자 동맹 관계"라 하고, 세 부족이 서로 적대 관계인 경우를 "삼자 적대 관계"라 하자.

이 때, 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을 만족하고, 같은 부족 쌍이 여러 번 주어지는 경우는 없다.

입력으로 주어지지 않은 부족 쌍은 적대관계라고 가정한다.

출력

각 테스트 케이스에 대해 한 줄에 동맹-반동맹 계수를 출력한다.

서브태스크 1 (4점)

  • 3 ≤ N ≤ 200
  • 1 ≤ M ≤ min(1,000, N × (N-1)/2)

서브태스크 2 (13점)

  • 3 ≤ N ≤ 5,000
  • 1 ≤ M ≤ min(1,000,000, N × (N-1)/2)

예제 입력 1

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

예제 출력 1

0
4
2
W3sicHJvYmxlbV9pZCI6IjE3Mjc1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViZDgwXHVjODcxIFx1YzgwNFx1YzdjMSIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNWI0XHViMjkwIFx1ZDU4OVx1YzEzMVx1YzVkMCBOXHVhYzFjXHVjNzU4IFx1Yzc5MVx1Yzc0MCBcdWJkODBcdWM4NzFcdWI0ZTRcdWM3NzQgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVkM2I4XHVjNzU4XHVjMGMxIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWI5N2MgXHViZDgwXHVjNWVjXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWJkODBcdWM4NzFcdWM3NDAgXHVjMTFjXHViODVjIFx1YjNkOVx1YjlmOSBcdWFkMDBcdWFjYzRcdWM3NzRcdWFjNzBcdWIwOTggXHVjMTFjXHViODVjIFx1YzgwMVx1YjMwMCBcdWFkMDBcdWFjYzRcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWFkMDBcdWFjYzRcdWIyOTQgXHViMzAwXHVjZTZkXHVjODAxXHVjNzc0XHViMmU0LiBcdWM5ODksIFx1YmQ4MFx1Yzg3MSBBXHViMjk0IFx1YmQ4MFx1Yzg3MSBCXHViOTdjIFx1YjNkOVx1YjlmOVx1Yzc3NFx1Yjc3YyBcdWMwZGRcdWFjMDFcdWQ1NThcdWIwOTggQlx1YjI5NCBBXHViOTdjIFx1YzgwMVx1Yzc3NFx1Yjc3YyBcdWMwZGRcdWFjMDFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViZDgwXHVjODcxIEFcdWM2NDAgXHViZDgwXHVjODcxIEJcdWFjMDAgXHViM2Q5XHViOWY5XHVjNzc0XHVhY2UwLCBcdWJkODBcdWM4NzEgQlx1YzY0MCBcdWJkODBcdWM4NzEgQ1x1YWMwMCBcdWIzZDlcdWI5ZjlcdWM3NzRcdWI3N2NcdWIzYzQgXHViZDgwXHVjODcxIEFcdWM2NDAgXHViZDgwXHVjODcxIENcdWFjMDAgXHVjODAxXHViMzAwIFx1YWQwMFx1YWNjNFx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3ODRcdWM3NThcdWM3NTggXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWMxMzggXHViZDgwXHVjODcxXHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYywgXHVjMTM4IFx1YmQ4MFx1Yzg3MVx1Yzc3NCBcdWMxMWNcdWI4NWMgXHViM2Q5XHViOWY5IFx1YWQwMFx1YWNjNFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWI5N2MgJnF1b3Q7XHVjMGJjXHVjNzkwIFx1YjNkOVx1YjlmOSBcdWFkMDBcdWFjYzQmcXVvdDtcdWI3N2MgXHVkNTU4XHVhY2UwLCBcdWMxMzggXHViZDgwXHVjODcxXHVjNzc0IFx1YzExY1x1Yjg1YyBcdWM4MDFcdWIzMDAgXHVhZDAwXHVhY2M0XHVjNzc4IFx1YWNiZFx1YzZiMFx1Yjk3YyAmcXVvdDtcdWMwYmNcdWM3OTAgXHVjODAxXHViMzAwIFx1YWQwMFx1YWNjNCZxdW90O1x1Yjc3YyBcdWQ1NThcdWM3OTAuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzc0IFx1YjU0YywgTlx1YWMxY1x1Yzc1OCBcdWJkODBcdWM4NzEgXHViMGI0XHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggJnF1b3Q7XHVjMGJjXHVjNzkwIFx1YjNkOVx1YjlmOSBcdWFkMDBcdWFjYzQmcXVvdDtcdWM2NDAgJnF1b3Q7XHVjMGJjXHVjNzkwIFx1YzgwMVx1YjMwMCBcdWFkMDBcdWFjYzQmcXVvdDtcdWI0ZTRcdWM3NDQgXHVjODA0XHViZDgwIFx1ZDU2OVx1ZDU1YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViNzdjLjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IE4gPSA1XHVjNzc0XHVhY2UwIFx1YmQ4MFx1Yzg3MTEtXHViZDgwXHVjODcxMiwgXHViZDgwXHVjODcxMS1cdWJkODBcdWM4NzEzLCBcdWJkODBcdWM4NzE0LVx1YmQ4MFx1Yzg3MTVcdWFjMDAgXHVjMTFjXHViODVjIFx1YjNkOVx1YjlmOSBcdWFkMDBcdWFjYzQsIFx1YjA5OFx1YmEzOFx1YzljMCBcdWJkODBcdWM4NzEgXHVjMzBkXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWM4MDFcdWIzMDAgXHVhZDAwXHVhY2M0XHViNzdjXHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU1OFx1Yzc5MC4gXHVjNzc0IFx1YWNiZFx1YzZiMCAoMiwgMywgNClcdWM2NDAgKDIsIDMsIDUpIFx1YWMwMCAmcXVvdDtcdWMwYmNcdWM3OTAgXHVjODAxXHViMzAwIFx1YWQwMFx1YWNjNCZxdW90O1x1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWFjZTAsICZxdW90O1x1YzBiY1x1Yzc5MCBcdWIzZDlcdWI5ZjkgXHVhZDAwXHVhY2M0JnF1b3Q7XHViMjk0IFx1YzVjNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHViMmY1XHVjNzQwIDJcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWI5NzggXHVjNjA4XHViODVjJm5ic3A7TiA9IDVcdWM3NzRcdWFjZTAgXHViZDgwXHVjODcxMS1cdWJkODBcdWM4NzEyLCBcdWJkODBcdWM4NzEyLVx1YmQ4MFx1Yzg3MTMsIFx1YmQ4MFx1Yzg3MTEtXHViZDgwXHVjODcxM1x1Yzc3NCBcdWIzZDlcdWI5ZjlcdWM3NzggXHVhY2JkXHVjNmIwICgxLCAyLCAzKVx1Yzc0MCAmcXVvdDtcdWMwYmNcdWM3OTAgXHViM2Q5XHViOWY5IFx1YWQwMFx1YWNjNCZxdW90O1x1Yzc3NFx1YWNlMCwmbmJzcDsoMSwgNCwgNSksICgyLCA0LCA1KSwgKDMsIDQsIDUpXHViMjk0ICZxdW90O1x1YzBiY1x1Yzc5MCBcdWM4MDFcdWIzMDAgXHVhZDAwXHVhY2M0JnF1b3Q7XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWIyZjVcdWM3NDAgNFx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0ICgxICZsZTsgVCAmbGU7IDEwKS48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHVjY2FiIFx1YzkwNFx1YzVkMCBOLCBNXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODQgXHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwXHVjMTFjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggeCwgeVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAgXHVjNzc0XHViMjk0IHhcdWM2NDAgeVx1YWMwMCBcdWIzZDlcdWI5ZjlcdWM3ODRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YjNkOVx1YjlmOSBcdWFkMDBcdWFjYzRcdWIyOTQgXHVjNWI4XHVjODFjXHViMDk4IDEgJmxlOyZuYnNwO3ggJmx0OyB5ICZsZTsmbmJzcDtOXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YWNlMCwgXHVhYzE5XHVjNzQwIFx1YmQ4MFx1Yzg3MSBcdWMzMGRcdWM3NzQgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWJkODBcdWM4NzEgXHVjMzBkXHVjNzQwIFx1YzgwMVx1YjMwMFx1YWQwMFx1YWNjNFx1Yjc3Y1x1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NWNcdWIyZTQuPFwvc3Ryb25nPjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YjNkOVx1YjlmOS1cdWJjMThcdWIzZDlcdWI5ZjkgXHVhY2M0XHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQiLCJzdWJ0YXNrMSI6Ijx1bD5cclxuXHQ8bGk+MyAmbGU7IE4gJmxlOyAyMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE0gJmxlOyBtaW4oMSwwMDAsIE4gJnRpbWVzOyAoTi0xKVwvMik8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2syIjoiPHVsPlxyXG5cdDxsaT4zICZsZTsgTiAmbGU7IDUsMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBNICZsZTsgbWluKDEsMDAwLDAwMCwgTiAmdGltZXM7IChOLTEpXC8yKTxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMTcyNzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmliYWwgd2FyIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBhcmUgTiBkaWZmZXJlbnQgdHJpYmVzIGluIGEgY291bnR5LCBudW1iZXJlZCBmcm9tIDEgdG8gTi48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Gb3IgYW55IHR3byBkaWZmZXJlbnQgdHJpYmVzLCB0aGV5IGFyZSBlaXRoZXIgaW4gYWxsaWFuY2Ugb3IgaG9zdGlsaXR5LiBUaGVzZSByZWxhdGlvbnNoaXBzIGFyZSBzeW1tZXRyaWMuPFwvbGk+XHJcblx0PGxpPk5vdGUgdGhhdCBldmVuIGlmIHRyaWJlIEEgYW5kIEIgYXJlIGFsbGllcyBhbmQgQiBhbmQgQyBhcmUgYWxsaWVzLCB0cmliZSBBIGFuZCBDIGNhbiBiZSBob3N0aWxlIHRvIGVhY2ggb3RoZXIuPFwvbGk+XHJcblx0PGxpPkZvciB0aHJlZSBkaWZmZXJlbnQgdHJpYmVzLCBpZiBhbGwgb2YgdGhlbSBhcmUgaW4gYW4gYWxsaWFuY2UsIHdlIGNhbGwgdGhlbSBhcyBpbiAmcXVvdDszLXdheSBhbGxpYW5jZSZxdW90OzsgU2ltaWxhcmx5LCBpZiBhbGwgb2YgdGhlbSBhcmUgaW4gaG9zdGlsaXR5LCB3ZSBjYWxsIHRoZW0gYXMgaW4gJnF1b3Q7My13YXkgaG9zdGlsaXR5JnF1b3Q7LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkdpdmVuIHRoZSByZWxhdGlvbnNoaXBzIGJldHdlZW4gTiB0cmliZXMsIHJldHVybiB0aGUgc3VtIG9mIGFsbCBvZiB0aGUgMy13YXkgYWxsaWFuY2VzIGFuZCAzLXdheSBob3N0aWxpdGllcy48XC9wPlxyXG5cclxuPHA+Rm9yIGluc3RhbmNlLCBsZXQgTiA9IDUgYW5kICgxLCAyKSwgKDEsIDMpLCBhbmQgKDQsIDUpIHJlcHJlc2VudCAzIGFsbGlhbmNlIHJlbGF0aW9uc2hpcHMgKGFsbCBvdGhlciBwYWlycyBhcmUgcGFpcndpc2UgZW5lbWllcykuIEluIHRoaXMgY2FzZSAoMiwgMywgNCkgYW5kICgyLCAzLCA1KSBhcmUgJnF1b3Q7My13YXkgaG9zdGlsaXR5JnF1b3Q7LCBhbmQgdGhlcmUgaXMgbm8gJnF1b3Q7My13YXkgYWxsaWFuY2UmcXVvdDsuIEhlbmNlIHRoZSBhbnN3ZXImbmJzcDtpcyAyLjxcL3A+XHJcblxyXG48cD5JbiBhbm90aGVyIGV4YW1wbGUsIGxldCBOID0gNSBhbmQgKDEsIDIpLCAoMiwgMyksIGFuZCAoMSwgMykgcmVwcmVzZW50IDMgYWxsaWFuY2UgcmVsYXRpb25zaGlwcyAoYWdhaW4sIGFsbCBvdGhlcnMgYXJlIHBhaXJ3aXNlIGVuZW1pZXMpLiBJbiB0aGlzIGNhc2UsICgxLCAyLCAzKSBpcyBhICZxdW90OzMtd2F5IGFsbGlhbmNlJnF1b3Q7IGFuZCAoMSwgNCwgNSksICgyLCA0LCA1KSwgYW5kICgzLCA0LCA1KSBhcmUgJnF1b3Q7My13YXkgaG9zdGlsaXR5JnF1b3Q7LiBUaGUgYW5zd2VyIGlzIDQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSB3aWxsIGNvbnRhaW4gdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBUICgxICZsZTsmbmJzcDtUICZsZTsgMTApLjxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZSBmaXJzdCBsaW5lIHdpbGwgY29udGFpbiBOIGFuZCBNIHNlcGFyYXRlZCBieSBhIHdoaXRlc3BhY2UuPFwvcD5cclxuXHJcbjxwPkZvciB0aGUgbmV4dCBNIGxpbmVzLCBlYWNoIGxpbmUgd2lsbCBjb250YWluIHR3byBpbnRlZ2VycyB4IGFuZCB5IHN1Y2ggdGhhdCB0cmliZXMgeCBhbmQgeSBhcmUgYWxsaWVzLiBZb3UgY2FuIGFzc3VtZSB0aGF0IDEgJmxlOyZuYnNwO3ggJmx0OyB5ICZsZTsmbmJzcDtOIGZvciBhbGwgTSBsaW5lcywgYW5kIG5vIGR1cGxpY2F0ZSBwYWlycyB3aWxsIGJlIHByb3ZpZGVkIGluIHRoZSBpbnB1dC4gPHN0cm9uZz5Bc3N1bWUgdGhhdCBhbGwgcGFpcnMgb2YgdHJpYmVzIHRoYXQgYXJlIG5vdCBnaXZlbiBpbiB0aGUgaW5wdXQgYXJlIHBhaXJ3aXNlIGVuZW1pZXMuJm5ic3A7PFwvc3Ryb25nPjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSAzLXdheSBBRSBOdW1iZXIgaW4gYSBzaW5nbGUgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQiLCJzdWJ0YXNrMSI6Ijx1bD5cclxuXHQ8bGk+MyAmbGU7IE4gJmxlOyAyMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IE0gJmxlOyBtaW4oMSwwMDAsIE4gJnRpbWVzOyAoTi0xKVwvMik8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2syIjoiPHVsPlxyXG5cdDxsaT4zICZsZTsgTiAmbGU7IDUsMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBNICZsZTsgbWluKDEsMDAwLDAwMCwgTiAmdGltZXM7IChOLTEpXC8yKTxcL2xpPlxyXG48XC91bD5cclxuIn1d

채점

  • 예제는 채점하지 않는다.