시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 989 404 326 41.688%

문제

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

W3sicHJvYmxlbV9pZCI6IjI0MjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NWNcdWM3MjRcdWM4MTVcdWM3NzQgXHVjNzc0XHVkMGM4XHViOWFjXHVjNTQ0XHVjNWQwIFx1YWMwMFx1YzExYyBcdWM1NDRcdWM3NzRcdWMyYTRcdWQwNmNcdWI5YmNcdWM3NDQgXHVjMGFjXHViYTM5XHViMjk0XHViMzcwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1NWNcdWM3MjRcdWM4MTVcdWFjZmMgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzQwIFx1Yzc3NFx1ZDBjOFx1YjlhY1x1YzU0NFx1Yjg1YyBcdWJjMjlcdWQ1NTkgXHVjNWVjXHVkNTg5XHVjNzQ0IFx1YWMxNFx1YjJlNC4gXHVjNzc0XHVkMGM4XHViOWFjXHVjNTQ0XHViMjk0IFx1YjM2NVx1YjJlNC4gXHVjNzI0XHVjODE1XHVjNzc0XHVjNjQwIFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1Yzc0MCBcdWM1NDRcdWM3NzRcdWMyYTRcdWQwNmNcdWI5YmNcdWM3NDQgXHVjMGFjXHViYTM5XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVjNTQ0XHVjNzc0XHVjMmE0XHVkMDZjXHViOWJjIFx1YWMwMFx1YWM4Y1x1YzVkMFx1YjI5NCBOXHVjODg1XHViOTU4XHVjNzU4IFx1YzU0NFx1Yzc3NFx1YzJhNFx1ZDA2Y1x1YjliY1x1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM1NDRcdWM3NzRcdWMyYTRcdWQwNmNcdWI5YmNcdWM3NDAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzhcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWM4ODVcdWI5NThcdWM3NTggXHVjNTQ0XHVjNzc0XHVjMmE0XHVkMDZjXHViOWJjXHVjNzQ0IFx1ZDU2OFx1YWVkOFx1YmEzOVx1YzczY1x1YmE3NCwgXHViOWRiXHVjNzc0IFx1YzU0NFx1YzhmYyBcdWQ2MTVcdWQzYjhcdWM1YzZcdWM1YjQgXHVjOWM0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgXHVjNzI0XHVjODE1XHVjNzc0XHViMjk0IFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWFjYmRcdWM2YjBcdWI5N2MgXHVkNTNjXHVkNTU4XHViYTc0XHVjMTFjIFx1YzU0NFx1Yzc3NFx1YzJhNFx1ZDA2Y1x1YjliY1x1Yzc0NCAzXHVhYzAwXHVjOWMwIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjMTIwXHVkMGRkXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWJhODcgXHVhYzAwXHVjOWMwXHVjNzc4XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzQwIFx1YzU0NFx1Yzc3NFx1YzJhNFx1ZDA2Y1x1YjliYyBcdWM4ODVcdWI5NThcdWM3NTggXHVjMjE4XHVjNzc0XHVhY2UwLCBNXHVjNzQwIFx1YzExZVx1YzViNFx1YmEzOVx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MThcdWIyOTQgXHVjODcwXHVkNTY5XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjNTQ0XHViNzk4IE1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzExZVx1YzViNFx1YmEzOVx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MThcdWIyOTQgXHVjODcwXHVkNTY5XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWQ1NjlcdWM3NDAgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViMDk4XHVjNjI0XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMjAwLCAwICZsZTsgTSAmbGU7IDEwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwLCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYzI5XHViYzk1XHVjNzc0IFx1Y2QxZCBcdWJhODcgXHVhYzFjIFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjVcdWFjMWNcdWM3NTggXHVjNTQ0XHVjNzc0XHVjMmE0XHVkMDZjXHViOWJjXHVhY2ZjIDNcdWFjMDBcdWM5YzAgXHVjMTFlXHVjNWI0XHViYTM5XHVjNzNjXHViYTc0IFx1YzU0OFx1YjQxOFx1YjI5NCBcdWM4NzBcdWQ1NjlcdWM3NzQgXHVjNzg4XHViMmU0LiAxXHViYzg4XHVjNzQwIDJcdWJjODggM1x1YmM4OFx1YWNmYyBcdWMxMWVcdWM3M2NcdWJhNzQgXHVjNTQ4XHViNDE4XHVhY2UwLCAzXHViYzg4XHVjNzQwIDRcdWJjODhcdWFjZmMgXHVjMTFlXHVjNzNjXHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjICgxIDQgNSksICgyIDMgNSksICgyIDQgNSkgM1x1YWMwMFx1YzljMCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjQyMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkljZSBDcmVhbSIsImRlc2NyaXB0aW9uIjoiPHA+UmFzbXVzIGFuZCBoaXMgZnJpZW5kcyBhcmUgb24gdmFjYXRpb24gaW4gSXRhbHkuIFNpbmNlIHRoZXkgYXJlIHN1ZmZlcmluZyBmcm9tIHRoZSBoZWF0LCB0aGV5IGRlY2lkZSB0byBidXkgc29tZSBpY2UgY3JlYW0uIFRoZXJlIGFyZSBOIFx1ZmIwMmF2b3JzIG9mIGljZSBjcmVhbSBhdmFpbGFibGU7IFx1ZmIwMmF2b3JzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gTi4gSG93ZXZlciwgc29tZSBwYWlyaW5ncyBvZiBcdWZiMDJhdm9ycyBzaG91bGQgYmUgYXZvaWRlZDsgb3RoZXJ3aXNlLCB0aGUgdGFzdGUgd291bGQgYmUgdW5wbGVhc2FudC4gUmFzbXVzIHdhbnRzIHRvIGtub3cgaG93IG1hbnkgd2F5cyB0aGVyZSBhcmUgdG8gY2hvb3NlIHRocmVlIGRpZmZlcmVudCBcdWZiMDJhdm9ycyB3aXRob3V0IGFueSBzdWNoIGltcG9zc2libGUgcGFpcmluZy4gVGhlIG9yZGVyIG9mIFx1ZmIwMmF2b3JzIGlzIG5vdCB0YWtlbiBpbnRvIGFjY291bnQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIG5vbi1uZWdhdGl2ZSBpbnRlZ2VycyBOIGFuZCBNLCB0aGUgbnVtYmVyIG9mIFx1ZmIwMmF2b3JzIGFuZCB0aGUgbnVtYmVyIG9mIGltcG9zc2libGUgcGFpcmluZ3MuIEVhY2ggb2YgdGhlIE0gZm9sbG93aW5nIGxpbmVzIGRlc2NyaWJlcyBhbiBpbXBvc3NpYmxlIHBhaXJpbmcgYW5kIGNvbnRhaW5zIHR3byBkaWZmZXJlbnQgXHVmYjAyYXZvciBudW1iZXJzLiBObyBpbXBvc3NpYmxlIHBhaXJpbmcgd2lsbCBhcHBlYXIgdHdpY2UuPFwvcD5cclxuXHJcbjxwPjEgJmxlOyBOICZsZTsgMjAwLjxiciBcLz5cclxuMCAmbGU7IE0gJmxlOyAxMCAwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gYSBzaW5nbGUgaW50ZWdlcjogdGhlIG51bWJlciBvZiBwb3NzaWJsZSBjaG9pY2VzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 2번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: rms uss01