시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB300805628.866%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

3 4
1 2
1 3
2 2
2 3

예제 출력 1

1

예제 입력 2

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

예제 출력 2

3
W3sicHJvYmxlbV9pZCI6IjMwOTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MDFcdWQ2NTRcdWM4MWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjExM1x1Yzc0MCBcdWFjMTVcdWM3NzQgXHVjNzg4XHViMjk0IFx1YjA5OFx1Yjc3Y1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWMxNVx1Yzc1OCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWIyOTQgXHViOWM4XHVjNzQ0XHVjNzc0IE5cdWFjMWMsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMFx1YjNjNCBOXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVhYzAxIFx1YjljOFx1Yzc0NFx1Yzc0MCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzY3Y1x1Y2FiZCBcdWI5YzhcdWM3NDQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YzY0MCBcdWM2MjRcdWI5NzhcdWNhYmQgXHViOWM4XHVjNzQ0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YmMzMFx1YjI5NCBcdWNkMWQgTVx1YWMxY1x1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YzU5MVx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNkMWQgNFx1YWMxYyBcdWI5YzhcdWM3NDRcdWM1ZDBcdWMxMWMgXHVjNjAxXHVkNjU0XHVjODFjXHViOTdjIFx1YWMxY1x1Y2Q1Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzY3Y1x1Y2FiZCBcdWI5YzhcdWM3NDRcdWM1ZDBcdWMxMWMgMlx1YWMxYywgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjljOFx1Yzc0NFx1YzVkMFx1YzExYyAyXHVhYzFjXHViOTdjIFx1YWNlMFx1Yjk3NFx1YmE3MCwgXHVjNjdjXHVjYWJkIFx1YjljOFx1Yzc0NFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjljOFx1Yzc0NFx1YWNmYyBcdWJjMzBcdWI4NWMgXHVjOWMxXHVjODExIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDFcdWQ2NTRcdWM4MWNcdWI5N2MgXHVhYzFjXHVjZDVjXHVkNTYwIFx1YjljOFx1Yzc0NFx1Yzc0NCBcdWFjZTBcdWI5NzRcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YzIxOCBOICgyICZsZTsgTiAmbGU7IDEwMDApXHVhY2ZjIFx1YmMzMFx1Yzc1OCBcdWMyMTggTSAoNCAmbGU7IE0gJmxlOyBOPHN1cD4yPFwvc3VwPilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzMwXHVhYzAwIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWI0NTAgXHViOWM4XHVjNzQ0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM2N2NcdWNhYmQsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzYwMVx1ZDY1NFx1YzgxY1x1Yjk3YyBcdWFjMWNcdWNkNWNcdWQ1NjAgXHViOWM4XHVjNzQ0XHVjNzQ0IFx1YWNlMFx1Yjk3NFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMDk2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU0VMQSIsImRlc2NyaXB0aW9uIjoiPHA+SW4gYSBmYXIgYXdheSBjb3VudHJ5IHRoZXJlIGlzIGEgd2lkZSByaXZlciwgTiB2aWxsYWdlcyBvbiB0aGUgbGVmdCBhbmQgTiB2aWxsYWdlcyBvbiB0aGUgcmlnaHQgc2lkZSBvZiB0aGlzIHJpdmVyIChkZW5vdGVkIGJ5IDEuLk4gb24gZWFjaCBzaWRlKS4gVGhlcmUgYXJlIGFsc28gTSBzbWFsbCBzaGlwcywgZWFjaCBvZiB0aGVtIGNvbm5lY3Rpbmcgb25lIHZpbGxhZ2UgZnJvbSB0aGUgbGVmdCBhbmQgb25lIHZpbGxhZ2UgZnJvbSB0aGUgcmlnaHQgc2lkZSAoaW4gYm90aCB3YXlzKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IGFyZSB0byBvcmdhbml6ZSBhIGZpbG0gZmVzdGl2YWwgaW4gZm91ciBvZiB0aGVzZSB2aWxsYWdlczogdHdvIGZyb20gdGhlIGxlZnQgYW5kIHR3byBmcm9tIHRoZSByaWdodCBzaWRlLiBFYWNoIHR3byBvZiB0aGVzZSBmb3VyIHZpbGxhZ2VzIG11c3QgYmUgY29ubmVjdGVkIGJ5IGEgc2hpcCAoZGlyZWN0bHkpIGlmIHRoZXkgYmVsb25nIHRvIG9wcG9zaXRlIHNpZGVzIG9mIHRoZSByaXZlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SGVscCB5b3Vyc2VsZiB0byBjaG9vc2UgdGhlc2UgZm91ciB2aWxsYWdlcyBhbmQgZmlyc3QgZmluZCBvdXQ7IGluIGhvdyBtYW55IHdheXMgY2FuIHlvdSBjaG9vc2UgdGhlbT8mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHBvc2l0aXZlIGludGVnZXJzIE4gKDIgJmxlOyBOICZsZTsgMTAwMCksIG51bWJlciBvZiB2aWxsYWdlcyBvbiBldmVyeSBzaWRlIG9mIHJpdmVyLCBhbmQgTSAoNCAmbGU7IE0gJmxlOyBOPHN1cD4yPFwvc3VwPiksIG51bWJlciBvZiBzbWFsbCBzaGlwcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TmV4dCBNIGxpbmVzIGNvbnRhaW4gdHdvIGludGVnZXJzLCBib3RoIGZyb20gaW50ZXJ2YWwgWzEsIE5dLCByZXByZXNlbnRpbmcgdGhlIHZpbGxhZ2UgZnJvbSB0aGUgbGVmdCBhbmQgdGhlIHZpbGxhZ2UgZnJvbSB0aGUgcmlnaHQgc2lkZSBjb25uZWN0ZWQgYnkgdGhpcyBzaGlwLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIG9uZSBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBwcmludCB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIHdheXMgdG8gY2hvb3NlIHZpbGxhZ2VzIGZvciB0aGUgZmVzdGl2YWwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=