시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1305 546 437 43.526%

문제

한윤정과 친구들은 이탈리아로 방학 여행을 갔다. 이탈리아는 덥다. 윤정이와 친구들은 아이스크림을 사먹기로 했다. 아이스크림 가게에는 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+XHJcbiIsImhpbnQiOiI8cD41XHVhYzFjXHVjNzU4IFx1YzU0NFx1Yzc3NFx1YzJhNFx1ZDA2Y1x1YjliY1x1YWNmYyAzXHVhYzAwXHVjOWMwIFx1YzExZVx1YzViNFx1YmEzOVx1YzczY1x1YmE3NCBcdWM1NDggXHViNDE4XHViMjk0IFx1Yzg3MFx1ZDU2OVx1Yzc3NCBcdWM3ODhcdWIyZTQuIDFcdWJjODhcdWM3NDAgMlx1YmM4OCAzXHViYzg4XHVhY2ZjIFx1YzExZVx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MThcdWFjZTAsIDNcdWJjODhcdWM3NDAgNFx1YmM4OFx1YWNmYyBcdWMxMWVcdWM3M2NcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgKDEgNCA1KSwgKDIgMyA1KSwgKDIgNCA1KVx1YzY0MCBcdWFjMTlcdWM3NzQgM1x1YWMwMFx1YzljMCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjQyMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkljZSBDcmVhbSIsImRlc2NyaXB0aW9uIjoiPHA+UmFzbXVzIGFuZCBoaXMgZnJpZW5kcyBhcmUgb24gdmFjYXRpb24gaW4gSXRhbHkuIFNpbmNlIHRoZXkgYXJlIHN1ZmZlcmluZyBmcm9tIHRoZSBoZWF0LCB0aGV5IGRlY2lkZSB0byBidXkgc29tZSBpY2UgY3JlYW0uIFRoZXJlIGFyZSBOIFx1ZmIwMmF2b3JzIG9mIGljZSBjcmVhbSBhdmFpbGFibGU7IFx1ZmIwMmF2b3JzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gTi4gSG93ZXZlciwgc29tZSBwYWlyaW5ncyBvZiBcdWZiMDJhdm9ycyBzaG91bGQgYmUgYXZvaWRlZDsgb3RoZXJ3aXNlLCB0aGUgdGFzdGUgd291bGQgYmUgdW5wbGVhc2FudC4gUmFzbXVzIHdhbnRzIHRvIGtub3cgaG93IG1hbnkgd2F5cyB0aGVyZSBhcmUgdG8gY2hvb3NlIHRocmVlIGRpZmZlcmVudCBcdWZiMDJhdm9ycyB3aXRob3V0IGFueSBzdWNoIGltcG9zc2libGUgcGFpcmluZy4gVGhlIG9yZGVyIG9mIFx1ZmIwMmF2b3JzIGlzIG5vdCB0YWtlbiBpbnRvIGFjY291bnQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIG5vbi1uZWdhdGl2ZSBpbnRlZ2VycyBOIGFuZCBNLCB0aGUgbnVtYmVyIG9mIFx1ZmIwMmF2b3JzIGFuZCB0aGUgbnVtYmVyIG9mIGltcG9zc2libGUgcGFpcmluZ3MuIEVhY2ggb2YgdGhlIE0gZm9sbG93aW5nIGxpbmVzIGRlc2NyaWJlcyBhbiBpbXBvc3NpYmxlIHBhaXJpbmcgYW5kIGNvbnRhaW5zIHR3byBkaWZmZXJlbnQgXHVmYjAyYXZvciBudW1iZXJzLiBObyBpbXBvc3NpYmxlIHBhaXJpbmcgd2lsbCBhcHBlYXIgdHdpY2UuPFwvcD5cclxuXHJcbjxwPjEgJmxlOyBOICZsZTsgMjAwLjxiciBcLz5cclxuMCAmbGU7IE0gJmxlOyAxMCAwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlcjogdGhlIG51bWJlciBvZiBwb3NzaWJsZSBjaG9pY2VzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 2번