시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1800 787 599 43.979%

문제

한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 N종류의 아이스크림이 있다. 모든 아이스크림은 1부터 N까지 번호가 매겨져있다. 어떤 종류의 아이스크림을 함께먹으면, 맛이 아주 형편없어진다. 따라서 윤정이는 이러한 경우를 피하면서 아이스크림을 3가지 선택하려고 한다. 이때, 선택하는 방법이 몇 가지인지 구하려고 한다.

입력

첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 이상 나오지 않는다. (1 ≤ N ≤ 200, 0 ≤ M ≤ 10,000)

출력

첫째 줄에, 가능한 방법이 총 몇 개 있는지 출력한다.

예제 입력 1

5 3
1 2
3 4
1 3

예제 출력 1

3

힌트

5개의 아이스크림과 3가지 섞어먹으면 안 되는 조합이 있다. 1번은 2번 3번과 섞으면 안되고, 3번은 4번과 섞으면 안 된다. 따라서 (1 4 5), (2 3 5), (2 4 5)와 같이 3가지 방법이 있다.

W3sicHJvYmxlbV9pZCI6IjI0MjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NWNcdWM3MjRcdWM4MTVcdWM3NzQgXHVjNzc0XHVkMGM4XHViOWFjXHVjNTQ0XHVjNWQwIFx1YWMwMFx1YzExYyBcdWM1NDRcdWM3NzRcdWMyYTRcdWQwNmNcdWI5YmNcdWM3NDQgXHVjMGFjXHViYTM5XHViMjk0XHViMzcwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NWNcdWM3MjRcdWM4MTVcdWFjZmMgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzQwIFx1Yzc3NFx1ZDBjOFx1YjlhY1x1YzU0NFx1Yjg1YyBcdWJjMjlcdWQ1NTkgXHVjNWVjXHVkNTg5XHVjNzQ0IFx1YWMxNFx1YjJlNC4gXHVjNzc0XHVkMGM4XHViOWFjXHVjNTQ0XHViMjk0IFx1YjM2NVx1YjJlNC4gXHVjNzI0XHVjODE1XHVjNzc0XHVjNjQwIFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1Yzc0MCBcdWM1NDRcdWM3NzRcdWMyYTRcdWQwNmNcdWI5YmNcdWM3NDQgXHVjMGFjXHViYTM5XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVjNTQ0XHVjNzc0XHVjMmE0XHVkMDZjXHViOWJjIFx1YWMwMFx1YWM4Y1x1YzVkMFx1YjI5NCBOXHVjODg1XHViOTU4XHVjNzU4IFx1YzU0NFx1Yzc3NFx1YzJhNFx1ZDA2Y1x1YjliY1x1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM1NDRcdWM3NzRcdWMyYTRcdWQwNmNcdWI5YmNcdWM3NDAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzhcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWM4ODVcdWI5NThcdWM3NTggXHVjNTQ0XHVjNzc0XHVjMmE0XHVkMDZjXHViOWJjXHVjNzQ0IFx1ZDU2OFx1YWVkOFx1YmEzOVx1YzczY1x1YmE3NCwgXHViOWRiXHVjNzc0IFx1YzU0NFx1YzhmYyBcdWQ2MTVcdWQzYjhcdWM1YzZcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM3MjRcdWM4MTVcdWM3NzRcdWIyOTQgXHVjNzc0XHViN2VjXHVkNTVjIFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWQ1M2NcdWQ1NThcdWJhNzRcdWMxMWMgXHVjNTQ0XHVjNzc0XHVjMmE0XHVkMDZjXHViOWJjXHVjNzQ0IDNcdWFjMDBcdWM5YzAgXHVjMTIwXHVkMGRkXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YmE4NyBcdWFjMDBcdWM5YzBcdWM3NzhcdWM5YzAgXHVhZDZjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4IE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHVjNTQ0XHVjNzc0XHVjMmE0XHVkMDZjXHViOWJjIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWMyMThcdWM3NzRcdWFjZTAsIE1cdWM3NDAgXHVjMTFlXHVjNWI0XHViYTM5XHVjNzNjXHViYTc0IFx1YzU0OCBcdWI0MThcdWIyOTQgXHVjODcwXHVkNTY5XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjNTQ0XHViNzk4IE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzExZVx1YzViNFx1YmEzOVx1YzczY1x1YmE3NCBcdWM1NDggXHViNDE4XHViMjk0IFx1Yzg3MFx1ZDU2OVx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMTlcdWM3NDAgXHVjODcwXHVkNTY5XHVjNzQwIFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YjA5OFx1YzYyNFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDIwMCwgMCAmbGU7IE0gJmxlOyAxMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCwgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWNkMWQgXHViYTg3IFx1YWMxYyBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD41XHVhYzFjXHVjNzU4IFx1YzU0NFx1Yzc3NFx1YzJhNFx1ZDA2Y1x1YjliY1x1YWNmYyAzXHVhYzAwXHVjOWMwIFx1YzExZVx1YzViNFx1YmEzOVx1YzczY1x1YmE3NCBcdWM1NDggXHViNDE4XHViMjk0IFx1Yzg3MFx1ZDU2OVx1Yzc3NCBcdWM3ODhcdWIyZTQuIDFcdWJjODhcdWM3NDAgMlx1YmM4OCAzXHViYzg4XHVhY2ZjIFx1YzExZVx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MThcdWFjZTAsIDNcdWJjODhcdWM3NDAgNFx1YmM4OFx1YWNmYyBcdWMxMWVcdWM3M2NcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjICgxIDQgNSksICgyIDMgNSksICgyIDQgNSlcdWM2NDAgXHVhYzE5XHVjNzc0IDNcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI0MjIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJY2UgQ3JlYW0iLCJkZXNjcmlwdGlvbiI6IjxwPlJhc211cyBhbmQgaGlzIGZyaWVuZHMgYXJlIG9uIHZhY2F0aW9uIGluIEl0YWx5LiBTaW5jZSB0aGV5IGFyZSBzdWZmZXJpbmcgZnJvbSB0aGUgaGVhdCwgdGhleSBkZWNpZGUgdG8gYnV5IHNvbWUgaWNlIGNyZWFtLiBUaGVyZSBhcmUgTiBcdWZiMDJhdm9ycyBvZiBpY2UgY3JlYW0gYXZhaWxhYmxlOyBcdWZiMDJhdm9ycyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIE4uIEhvd2V2ZXIsIHNvbWUgcGFpcmluZ3Mgb2YgXHVmYjAyYXZvcnMgc2hvdWxkIGJlIGF2b2lkZWQ7IG90aGVyd2lzZSwgdGhlIHRhc3RlIHdvdWxkIGJlIHVucGxlYXNhbnQuIFJhc211cyB3YW50cyB0byBrbm93IGhvdyBtYW55IHdheXMgdGhlcmUgYXJlIHRvIGNob29zZSB0aHJlZSBkaWZmZXJlbnQgXHVmYjAyYXZvcnMgd2l0aG91dCBhbnkgc3VjaCBpbXBvc3NpYmxlIHBhaXJpbmcuIFRoZSBvcmRlciBvZiBcdWZiMDJhdm9ycyBpcyBub3QgdGFrZW4gaW50byBhY2NvdW50LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBub24tbmVnYXRpdmUgaW50ZWdlcnMgTiBhbmQgTSwgdGhlIG51bWJlciBvZiBcdWZiMDJhdm9ycyBhbmQgdGhlIG51bWJlciBvZiBpbXBvc3NpYmxlIHBhaXJpbmdzLiBFYWNoIG9mIHRoZSBNIGZvbGxvd2luZyBsaW5lcyBkZXNjcmliZXMgYW4gaW1wb3NzaWJsZSBwYWlyaW5nIGFuZCBjb250YWlucyB0d28gZGlmZmVyZW50IFx1ZmIwMmF2b3IgbnVtYmVycy4gTm8gaW1wb3NzaWJsZSBwYWlyaW5nIHdpbGwgYXBwZWFyIHR3aWNlLjxcL3A+XHJcblxyXG48cD4xICZsZTsgTiAmbGU7IDIwMC48YnIgXC8+XHJcbjAgJmxlOyBNICZsZTsgMTAgMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIGEgc2luZ2xlIGludGVnZXI6IHRoZSBudW1iZXIgb2YgcG9zc2libGUgY2hvaWNlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 2번