시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 891 212 142 23.471%

문제

농부 존은 최근에 N*N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2≤N≤100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1,1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 

베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

입력

첫 번째 줄에는 N(2≤N≤100)과, M(1≤M≤20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다. 

출력

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

예제 입력 1

3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1

예제 출력 1

5

힌트

(1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으므로, (2, 3)위치에 있는 스위치는 누를 수 없다. 그러므로 불을 밝힐 수 있는 방의 최대 개수는 5이다. 

W3sicHJvYmxlbV9pZCI6IjExOTY3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViZDg4XHVjZjFjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxOGRcdWJkODAgXHVjODc0XHVjNzQwIFx1Y2Q1Y1x1YWRmY1x1YzVkMCBOKk5cdWFjMWNcdWM3NTggXHViYzI5XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWFjNzBcdWIzMDBcdWQ1NWMgXHVkNWRiXHVhYzA0XHVjNzQ0IFx1YzBjOFx1Yjg1YyBcdWM5YzBcdWM1YzhcdWIyZTQuIFx1YWMwMSBcdWJjMjlcdWM3NDAgKDEsIDEpXHViZDgwXHVkMTMwIChOLE4pXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzhcdWM3ODhcdWIyZTQoMiZsZTtOJmxlOzEwMCkuJm5ic3A7XHVjNWI0XHViNDYwXHVjNzQ0IFx1YmIzNFx1YzExY1x1YzZjY1x1ZDU1OFx1YjI5NCBcdWM1NTRcdWMxOGMgXHViY2EwXHVjMmRjXHViMjk0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHViYzI5XHVjNWQwIFx1YmQ4OFx1Yzc0NCBcdWJjMWRcdWQ3ODhcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjYTBcdWMyZGNcdWIyOTQgXHVjNzIwXHVjNzdjXHVkNTU4XHVhYzhjIFx1YmQ4OFx1Yzc3NCBcdWNmMWNcdWM4MzhcdWM3ODhcdWIyOTQgXHViYzI5XHVjNzc4Jm5ic3A7KDEsMSlcdWJjMjlcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTVjXHViMmU0LiBcdWM1YjRcdWI1YTQgXHViYzI5XHVjNWQwXHViMjk0IFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWM3NTggXHViZDg4XHVjNzQ0IFx1YjA0NFx1YWNlMCBcdWNmMjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHViMmVjXHViODI0XHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAoMSwgMSlcdWJjMjlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjg1YyAoMSwgMilcdWJjMjlcdWM3NTggXHViZDg4XHVjNzQ0IFx1YjA0NFx1YWNlMCBcdWNmMjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViY2EwXHVjMmRjXHViMjk0IFx1YmQ4OFx1Yzc3NCBcdWNmMWNcdWM4MzhcdWM3ODhcdWIyOTQgXHViYzI5XHVjNzNjXHViODVjXHViOWNjIFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHViYzI5XHVjNWQwXHVjMTFjXHViMjk0Jm5ic3A7XHVjMGMxXHVkNTU4XHVjODhjXHVjNmIwXHVjNWQwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJjMjlcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YmNhMFx1YzJkY1x1YWMwMCBcdWJkODhcdWM3NDQgXHVjZjI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTigyJmxlO04mbGU7MTAwKVx1YWNmYywgTSgxJmxlO00mbGU7MjAsMDAwKVx1Yzc3NCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YzkwNFx1YzVkMFx1YjI5NCBcdWIxMjQgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCB4LCB5LCBhLCBiXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKHgsIHkpXHViYzI5XHVjNWQwXHVjMTFjIChhLCBiKVx1YmMyOVx1Yzc1OCBcdWJkODhcdWM3NDQgXHVjZjFjXHVhY2UwIFx1YjA0YyBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC4gXHVkNTVjIFx1YmMyOVx1YzVkMCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWM3NTggXHVjMmE0XHVjNzA0XHVjZTU4XHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWQ1NThcdWIwOThcdWM3NTggXHViZDg4XHVjNzQ0IFx1Yzg3MFx1YzgwOFx1ZDU1OFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNTggXHVjNWVkXHVjMmRjJm5ic3A7XHVjNWVjXHViN2VjXHVhYzFjIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmNhMFx1YzJkY1x1YWMwMCBcdWJkODhcdWM3NDQgXHVjZjI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4oMSwgMSlcdWJjMjlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjg1YyAoMSwgMilcdWJjMjlcdWFjZmMgKDEsIDMpXHViYzI5XHVjNzU4IFx1YmQ4OFx1Yzc0NCBcdWNmMjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwICgxLCAzKVx1YzczY1x1Yjg1YyBcdWFjNzhcdWM1YjRcdWFjMDBcdWMxMWMgKDIsIDEpXHViYzI5XHVjNzU4IFx1YmQ4OFx1Yzc0NCBcdWNmMjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKDIsIDEpXHViYzI5XHVjNWQwXHVjMTFjXHViMjk0IFx1YjJlNFx1YzJkYyAoMiwgMilcdWJjMjlcdWM3NTggXHViZDg4XHVjNzQ0IFx1Y2YyNCBcdWMyMTggXHVjNzg4XHViMmU0LiAoMiwgMylcdWJjMjlcdWM3NDAgXHVjNWI0XHViNDUwXHVjNmNjXHVjMTFjIFx1YWMwOCBcdWMyMTggXHVjNWM2XHVjNzNjXHViYmMwXHViODVjLCAoMiwgMylcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWIyMDRcdWI5N2MgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVhZGY4XHViN2VjXHViYmMwXHViODVjIFx1YmQ4OFx1Yzc0NCBcdWJjMWRcdWQ3OTAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1YjI5NCA1XHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTE5NjciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTd2l0Y2hpbmcgb24gdGhlIExpZ2h0cyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaGFzIHJlY2VudGx5IGJ1aWx0IGFuIGVub3Jtb3VzIGJhcm4gY29uc2lzdGluZyBvZiBhbiBcXChOIFxcdGltZXMgTlxcKSBncmlkIG9mIHJvb21zIChcXCgyIFxcbGVxIE4gXFxsZXEgMTAwXFwpKSwgbnVtYmVyZWQgZnJvbSBcXCgoMSwxKVxcKSB1cCB0byBcXCgoTixOKVxcKS4gQmVpbmcgc29tZXdoYXQgYWZyYWlkIG9mIHRoZSBkYXJrLCBCZXNzaWUgdGhlIGNvdyB3YW50cyB0byB0dXJuIG9uIHRoZSBsaWdodHMgaW4gYXMgbWFueSByb29tcyBhcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+QmVzc2llIHN0YXJ0cyBpbiByb29tIFxcKCgxLDEpXFwpLCB0aGUgb25seSByb29tIHRoYXQgaXMgaW5pdGlhbGx5IGxpdC4gSW4gc29tZSByb29tcywgc2hlIHdpbGwgZmluZCBsaWdodCBzd2l0Y2hlcyB0aGF0IHNoZSBjYW4gdXNlIHRvIHRvZ2dsZSB0aGUgbGlnaHRzIGluIG90aGVyIHJvb21zOyBmb3IgZXhhbXBsZSB0aGVyZSBtaWdodCBiZSBhIHN3aXRjaCBpbiByb29tIFxcKCgxLDEpXFwpIHRoYXQgdG9nZ2xlcyB0aGUgbGlnaHRzIGluIHJvb20gXFwoKDEsMilcXCkuIEJlc3NpZSBjYW4gb25seSB0cmF2ZWwgdGhyb3VnaCBsaXQgcm9vbXMsIGFuZCBzaGUgY2FuIG9ubHkgbW92ZSBmcm9tIGEgcm9vbSBcXCgoeCx5KVxcKSB0byBpdHMgZm91ciBhZGphY2VudCBuZWlnaGJvcnMgXFwoKHgtMSx5KVxcKSwgXFwoKHgrMSx5KVxcKSwgXFwoKHgseS0xKVxcKSBhbmQgXFwoKHgseSsxKVxcKSAob3IgcG9zc2libHkgZmV3ZXIgbmVpZ2hib3JzIGlmIHRoaXMgcm9vbSBpcyBvbiB0aGUgYm91bmRhcnkgb2YgdGhlIGdyaWQpLjxcL3A+XHJcblxyXG48cD5QbGVhc2UgZGV0ZXJtaW5lIHRoZSBtYXhpbXVtIG51bWJlciBvZiByb29tcyBCZXNzaWUgY2FuIGlsbHVtaW5hdGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBpbnRlZ2VycyBcXChOXFwpIGFuZCBcXChNXFwpIChcXCgxIFxcbGVxIE0gXFxsZXEgMjAsMDAwXFwpKS48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgXFwoTVxcKSBsaW5lcyBlYWNoIGRlc2NyaWJlIGEgc2luZ2xlIGxpZ2h0IHN3aXRjaCB3aXRoIGZvdXIgaW50ZWdlcnMgXFwoeFxcKSwgXFwoeVxcKSwgXFwoYVxcKSwgXFwoYlxcKSwgdGhhdCBhIHN3aXRjaCBpbiByb29tIFxcKCh4LHkpXFwpIGNhbiBiZSB1c2VkIHRvIHRvZ2dsZSB0aGUgbGlnaHRzIGluIHJvb20gXFwoKGEsYilcXCkuIE11bHRpcGxlIHN3aXRjaGVzIG1heSBleGlzdCBpbiBhbnkgcm9vbSwgYW5kIG11bHRpcGxlIHN3aXRjaGVzIG1heSB0b2dnbGUgdGhlIGxpZ2h0cyBvZiBhbnkgcm9vbS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5BIHNpbmdsZSBsaW5lIGdpdmluZyB0aGUgbWF4aW11bSBudW1iZXIgb2Ygcm9vbXMgQmVzc2llIGNhbiBpbGx1bWluYXRlLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5IZXJlLCBCZXNzaWUgY2FuIHVzZSB0aGUgc3dpdGNoIGluIFxcKCgxLDEpXFwpIHRvIHR1cm4gb24gbGlnaHRzIGluIFxcKCgxLDIpXFwpJm5ic3A7YW5kIFxcKCgxLDMpXFwpLiBTaGUgY2FuIHRoZW4gd2FsayB0byBcXCgoMSwzKVxcKSBhbmQgdHVybiBvbiB0aGUgbGlnaHRzIGluIFxcKCgyLDEpXFwpLCBmcm9tIHdoaWNoIHNoZSBjYW4gdHVybiBvbiB0aGUgbGlnaHRzIGluIFxcKCgyLDIpXFwpLiBUaGUgc3dpdGNoIGluIFxcKCgyLDMpXFwpIGlzIGluYWNjZXNzaWJsZSB0byBoZXIsIGJlaW5nIGluIGFuIHVubGl0IHJvb20uIFNoZSBjYW4gdGhlcmVmb3JlIGlsbHVtaW5hdGUgYXQgbW9zdCA1IHJvb21zLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d