시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 890 356 294 41.119%

문제

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

W3sicHJvYmxlbV9pZCI6IjI0MjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NWNcdWM3MjRcdWM4MTVcdWM3NzQgXHVjNzc0XHVkMGM4XHViOWFjXHVjNTQ0XHVjNWQwXHVhYzAwXHVjMTFjIFx1YzU0NFx1Yzc3NFx1YzJhNFx1ZDA2Y1x1YjliY1x1Yzc0NCBcdWMwYWNcdWJhMzlcdWIyOTRcdWIzNzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDU1Y1x1YzcyNFx1YzgxNVx1YWNmYyBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM3NDAgXHVjNzc0XHVkMGM4XHViOWFjXHVjNTQ0XHViODVjIFx1YmMyOVx1ZDU1OSBcdWM1ZWNcdWQ1ODlcdWM3NDQgXHVhYzE0XHViMmU0LiBcdWM3NzRcdWQwYzhcdWI5YWNcdWM1NDRcdWIyOTQgXHViMzY1XHViMmU0LiBcdWM3MjRcdWM4MTVcdWM3NzRcdWM2NDAgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzQwIFx1YzU0NFx1Yzc3NFx1YzJhNFx1ZDA2Y1x1YjliY1x1Yzc0NCBcdWMwYWNcdWJhMzlcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWM1NDRcdWM3NzRcdWMyYTRcdWQwNmNcdWI5YmMgXHVhYzAwXHVhYzhjXHVjNWQwXHViMjk0IE5cdWM4ODVcdWI5NThcdWM3NTggXHVjNTQ0XHVjNzc0XHVjMmE0XHVkMDZjXHViOWJjXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzU0NFx1Yzc3NFx1YzJhNFx1ZDA2Y1x1YjliY1x1Yzc0MCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWM1NDRcdWM3NzRcdWMyYTRcdWQwNmNcdWI5YmNcdWM3NDQgXHVkNTY4XHVhZWQ4XHViYTM5XHVjNzNjXHViYTc0LCBcdWI5ZGJcdWM3NzQgXHVjNTQ0XHVjOGZjIFx1ZDYxNVx1ZDNiOFx1YzVjNlx1YzViNCBcdWM5YzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWM3MjRcdWM4MTVcdWM3NzRcdWIyOTQgXHVjNzc0XHViN2VjXHVkNTVjIFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWQ1M2NcdWQ1NThcdWJhNzRcdWMxMWMgXHVjNTQ0XHVjNzc0XHVjMmE0XHVkMDZjXHViOWJjXHVjNzQ0IDNcdWFjMDBcdWM5YzAgXHVjMTIwXHVkMGRkXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjMTIwXHVkMGRkXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWJhODdcdWFjMDBcdWM5YzBcdWM3NzhcdWM5YzAgXHVhZDZjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4IE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHVjNTQ0XHVjNzc0XHVjMmE0XHVkMDZjXHViOWJjIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWMyMThcdWM3NzRcdWFjZTAsIE1cdWM3NDAgXHVjMTFlXHVjNWI0XHViYTM5XHVjNzNjXHViYTc0IFx1YzU0OFx1YjQxOFx1YjI5NCBcdWM4NzBcdWQ1NjlcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM1NDRcdWI3OTggTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTFlXHVjNWI0XHViYTM5XHVjNzNjXHViYTc0IFx1YzU0OFx1YjQxOFx1YjI5NCBcdWM4NzBcdWQ1NjlcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1Yzg3MFx1ZDU2OVx1Yzc0MCBcdWI0NTAgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWIwOThcdWM2MjRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiAoMSZsdDs9TiZsdDs9MjAwLCAwJmx0Oz1NJmx0Oz0xMCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCwgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWNkMWQgXHViYTg3IFx1YWMxYyBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD41XHVhYzFjXHVjNzU4IFx1YzU0NFx1Yzc3NFx1YzJhNFx1ZDA2Y1x1YjliY1x1YWNmYyAzXHVhYzAwXHVjOWMwIFx1YzExZVx1YzViNFx1YmEzOVx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MThcdWIyOTQgXHVjODcwXHVkNTY5XHVjNzc0IFx1Yzc4OFx1YjJlNC4gMVx1YmM4OFx1Yzc0MCAyXHViYzg4IDNcdWJjODhcdWFjZmMgXHVjMTFlXHVjNzNjXHViYTc0IFx1YzU0OFx1YjQxOFx1YWNlMCwgM1x1YmM4OFx1Yzc0MCA0XHViYzg4XHVhY2ZjIFx1YzExZVx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyAoMSA0IDUpLCAoMiAzIDUpLCAoMiA0IDUpIDNcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI0MjIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJY2UgQ3JlYW0iLCJkZXNjcmlwdGlvbiI6IjxwPlJhc211cyBhbmQgaGlzIGZyaWVuZHMgYXJlIG9uIHZhY2F0aW9uIGluIEl0YWx5LiBTaW5jZSB0aGV5IGFyZSBzdWZmZXJpbmcgZnJvbSB0aGUgaGVhdCwgdGhleSBkZWNpZGUgdG8gYnV5IHNvbWUgaWNlIGNyZWFtLiBUaGVyZSBhcmUgTiBcdWZiMDJhdm9ycyBvZiBpY2UgY3JlYW0gYXZhaWxhYmxlOyBcdWZiMDJhdm9ycyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIE4uIEhvd2V2ZXIsIHNvbWUgcGFpcmluZ3Mgb2YgXHVmYjAyYXZvcnMgc2hvdWxkIGJlIGF2b2lkZWQ7IG90aGVyd2lzZSwgdGhlIHRhc3RlIHdvdWxkIGJlIHVucGxlYXNhbnQuIFJhc211cyB3YW50cyB0byBrbm93IGhvdyBtYW55IHdheXMgdGhlcmUgYXJlIHRvIGNob29zZSB0aHJlZSBkaWZmZXJlbnQgXHVmYjAyYXZvcnMgd2l0aG91dCBhbnkgc3VjaCBpbXBvc3NpYmxlIHBhaXJpbmcuIFRoZSBvcmRlciBvZiBcdWZiMDJhdm9ycyBpcyBub3QgdGFrZW4gaW50byBhY2NvdW50LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBub24tbmVnYXRpdmUgaW50ZWdlcnMgTiBhbmQgTSwgdGhlIG51bWJlciBvZiBcdWZiMDJhdm9ycyBhbmQgdGhlIG51bWJlciBvZiBpbXBvc3NpYmxlIHBhaXJpbmdzLiBFYWNoIG9mIHRoZSBNIGZvbGxvd2luZyBsaW5lcyBkZXNjcmliZXMgYW4gaW1wb3NzaWJsZSBwYWlyaW5nIGFuZCBjb250YWlucyB0d28gZGlmZmVyZW50IFx1ZmIwMmF2b3IgbnVtYmVycy4gTm8gaW1wb3NzaWJsZSBwYWlyaW5nIHdpbGwgYXBwZWFyIHR3aWNlLjxcL3A+XHJcblxyXG48cD4xICZsZTsgTiAmbGU7IDIwMC48YnIgXC8+XHJcbjAgJmxlOyBNICZsZTsgMTAgMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIGEgc2luZ2xlIGludGVnZXI6IHRoZSBudW1iZXIgb2YgcG9zc2libGUgY2hvaWNlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2011 2번

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