시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 159 33 22 22.917%

문제

넓은 강이 있는 나라가 있다. 강의 왼쪽에는 마을이 N개, 오른쪽에도 N개가 있으며, 각 마을은 1번부터 N번까지 번호가 매겨져 있다. 왼쪽 마을 중 하나와 오른쪽 마을 중 하나를 연결하는 배는 총 M개가 있고, 양방향으로 연결한다.

상근이는 총 4개 마을에서 영화제를 개최하려고 한다. 왼쪽 마을에서 2개, 오른쪽 마을에서 2개를 고르며, 왼쪽 마을은 모두 오른쪽 마을과 배로 직접 연결되어 있어야 한다.

영화제를 개최할 마을을 고르는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 마을의 수 N (2 ≤ N ≤ 1000)과 배의 수 M (4 ≤ M ≤ N2)이 주어진다.

다음 M개 줄에는 배가 연결하는 두 마을의 번호가 왼쪽, 오른쪽 순서대로 주어진다.

출력

영화제를 개최할 마을을 고르는 방법의 수를 출력한다.

예제 입력 1

3 7
1 1
1 3
2 1
2 3
3 1
3 2
3 3

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjMwOTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MDFcdWQ2NTRcdWM4MWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjExM1x1Yzc0MCBcdWFjMTVcdWM3NzQgXHVjNzg4XHViMjk0IFx1YjA5OFx1Yjc3Y1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWMxNVx1Yzc1OCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWIyOTQgXHViOWM4XHVjNzQ0XHVjNzc0IE5cdWFjMWMsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMFx1YjNjNCBOXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAxIFx1YjljOFx1Yzc0NFx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzY3Y1x1Y2FiZCBcdWI5YzhcdWM3NDQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YzY0MCBcdWM2MjRcdWI5NzhcdWNhYmQgXHViOWM4XHVjNzQ0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YmMzMFx1YjI5NCBcdWNkMWQgTVx1YWMxY1x1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YzU5MVx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNkMWQgNFx1YWMxYyBcdWI5YzhcdWM3NDRcdWM1ZDBcdWMxMWMgXHVjNjAxXHVkNjU0XHVjODFjXHViOTdjIFx1YWMxY1x1Y2Q1Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzY3Y1x1Y2FiZCBcdWI5YzhcdWM3NDRcdWM1ZDBcdWMxMWMgMlx1YWMxYywgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjljOFx1Yzc0NFx1YzVkMFx1YzExYyAyXHVhYzFjXHViOTdjIFx1YWNlMFx1Yjk3NFx1YmE3MCwgXHVjNjdjXHVjYWJkIFx1YjljOFx1Yzc0NFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjljOFx1Yzc0NFx1YWNmYyBcdWJjMzBcdWI4NWMgXHVjOWMxXHVjODExIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDFcdWQ2NTRcdWM4MWNcdWI5N2MgXHVhYzFjXHVjZDVjXHVkNTYwIFx1YjljOFx1Yzc0NFx1Yzc0NCBcdWFjZTBcdWI5NzRcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YzIxOCBOICgyICZsZTsgTiAmbGU7IDEwMDApXHVhY2ZjIFx1YmMzMFx1Yzc1OCBcdWMyMTggTSAoNCAmbGU7IE0gJmxlOyBOPHN1cD4yPFwvc3VwPilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzMwXHVhYzAwIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWI0NTAgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM2N2NcdWNhYmQsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzYwMVx1ZDY1NFx1YzgxY1x1Yjk3YyBcdWFjMWNcdWNkNWNcdWQ1NjAgXHViOWM4XHVjNzQ0XHVjNzQ0IFx1YWNlMFx1Yjk3NFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwOTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTRUxBIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBhIGZhciBhd2F5IGNvdW50cnkgdGhlcmUgaXMgYSB3aWRlIHJpdmVyLCBOIHZpbGxhZ2VzIG9uIHRoZSBsZWZ0IGFuZCBOIHZpbGxhZ2VzIG9uIHRoZSByaWdodCBzaWRlIG9mIHRoaXMgcml2ZXIgKGRlbm90ZWQgYnkgMS4uTiBvbiBlYWNoIHNpZGUpLiBUaGVyZSBhcmUgYWxzbyBNIHNtYWxsIHNoaXBzLCBlYWNoIG9mIHRoZW0gY29ubmVjdGluZyBvbmUgdmlsbGFnZSBmcm9tIHRoZSBsZWZ0IGFuZCBvbmUgdmlsbGFnZSBmcm9tIHRoZSByaWdodCBzaWRlIChpbiBib3RoIHdheXMpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIHRvIG9yZ2FuaXplIGEgZmlsbSBmZXN0aXZhbCBpbiBmb3VyIG9mIHRoZXNlIHZpbGxhZ2VzOiB0d28gZnJvbSB0aGUgbGVmdCBhbmQgdHdvIGZyb20gdGhlIHJpZ2h0IHNpZGUuIEVhY2ggdHdvIG9mIHRoZXNlIGZvdXIgdmlsbGFnZXMgbXVzdCBiZSBjb25uZWN0ZWQgYnkgYSBzaGlwIChkaXJlY3RseSkgaWYgdGhleSBiZWxvbmcgdG8gb3Bwb3NpdGUgc2lkZXMgb2YgdGhlIHJpdmVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5IZWxwIHlvdXJzZWxmIHRvIGNob29zZSB0aGVzZSBmb3VyIHZpbGxhZ2VzIGFuZCBmaXJzdCBmaW5kIG91dDsgaW4gaG93IG1hbnkgd2F5cyBjYW4geW91IGNob29zZSB0aGVtPyZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgTiAoMiAmbGU7IE4gJmxlOyAxMDAwKSwgbnVtYmVyIG9mIHZpbGxhZ2VzIG9uIGV2ZXJ5IHNpZGUgb2Ygcml2ZXIsIGFuZCBNICg0ICZsZTsgTSAmbGU7IE48c3VwPjI8XC9zdXA+KSwgbnVtYmVyIG9mIHNtYWxsIHNoaXBzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5OZXh0IE0gbGluZXMgY29udGFpbiB0d28gaW50ZWdlcnMsIGJvdGggZnJvbSBpbnRlcnZhbCBbMSwgTl0sIHJlcHJlc2VudGluZyB0aGUgdmlsbGFnZSBmcm9tIHRoZSBsZWZ0IGFuZCB0aGUgdmlsbGFnZSBmcm9tIHRoZSByaWdodCBzaWRlIGNvbm5lY3RlZCBieSB0aGlzIHNoaXAuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gb25lIGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHByaW50IHRoZSByZXF1aXJlZCBudW1iZXIgb2Ygd2F5cyB0byBjaG9vc2UgdmlsbGFnZXMgZm9yIHRoZSBmZXN0aXZhbC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=