시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 828 197 130 23.173%

문제

농부 존은 최근에 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+XHJcblxyXG48cD5cdWJjYTBcdWMyZGNcdWIyOTQgXHVjNzIwXHVjNzdjXHVkNTU4XHVhYzhjIFx1YmQ4OFx1Yzc3NCBcdWNmMWNcdWM4MzhcdWM3ODhcdWIyOTQgXHViYzI5XHVjNzc4Jm5ic3A7KDEsMSlcdWJjMjlcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTVjXHViMmU0LiBcdWM1YjRcdWI1YTQgXHViYzI5XHVjNWQwXHViMjk0IFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWM3NTggXHViZDg4XHVjNzQ0IFx1YjA0NFx1YWNlMCBcdWNmMjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHViMmVjXHViODI0XHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAoMSwgMSlcdWJjMjlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1Yjg1YyAoMSwgMilcdWJjMjlcdWM3NTggXHViZDg4XHVjNzQ0IFx1YjA0NFx1YWNlMCBcdWNmMjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViY2EwXHVjMmRjXHViMjk0IFx1YmQ4OFx1Yzc3NCBcdWNmMWNcdWM4MzhcdWM3ODhcdWIyOTQgXHViYzI5XHVjNzNjXHViODVjXHViOWNjIFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHViYzI5XHVjNWQwXHVjMTFjXHViMjk0Jm5ic3A7XHVjMGMxXHVkNTU4XHVjODhjXHVjNmIwXHVjNWQwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJjMjlcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YmNhMFx1YzJkY1x1YWMwMCBcdWJkODhcdWM3NDQgXHVjZjI0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYzI5XHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMmZcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOKDImbGU7TiZsZTsxMDApXHVhY2ZjLCBNKDEmbGU7TSZsZTsyMCwwMDApXHVjNzc0IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBNXHVjOTA0XHVjNWQwXHViMjk0IFx1YjEyNCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IHgsIHksIGEsIGJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoeCwgeSlcdWJjMjlcdWM1ZDBcdWMxMWMgKGEsIGIpXHViYzI5XHVjNzU4IFx1YmQ4OFx1Yzc0NCBcdWNmMWNcdWFjZTAgXHViMDRjIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LiBcdWQ1NWMgXHViYzI5XHVjNWQwIFx1YzVlY1x1YjdlY1x1YWMxY1x1Yzc1OCBcdWMyYTRcdWM3MDRcdWNlNThcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJkODhcdWM3NDQgXHVjODcwXHVjODA4XHVkNTU4XHViMjk0IFx1YzJhNFx1YzcwNFx1Y2U1OCBcdWM1ZWRcdWMyZGMmbmJzcDtcdWM1ZWNcdWI3ZWNcdWFjMWMgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViY2EwXHVjMmRjXHVhYzAwIFx1YmQ4OFx1Yzc0NCBcdWNmMjQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMyZlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaGludCI6IjxwPigxLCAxKVx1YmMyOVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMmE0XHVjNzA0XHVjZTU4XHViODVjICgxLCAyKVx1YmMyOVx1YWNmYyAoMSwgMylcdWJjMjlcdWM3NTggXHViZDg4XHVjNzQ0IFx1Y2YyNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgKDEsIDMpXHVjNzNjXHViODVjIFx1YWM3OFx1YzViNFx1YWMwMFx1YzExYyAoMiwgMSlcdWJjMjlcdWM3NTggXHViZDg4XHVjNzQ0IFx1Y2YyNCBcdWMyMTggXHVjNzg4XHViMmU0LiAoMiwgMSlcdWJjMjlcdWM1ZDBcdWMxMWNcdWIyOTQgXHViMmU0XHVjMmRjICgyLCAyKVx1YmMyOVx1Yzc1OCBcdWJkODhcdWM3NDQgXHVjZjI0IFx1YzIxOCBcdWM3ODhcdWIyZTQuICgyLCAzKVx1YmMyOVx1Yzc0MCBcdWM1YjRcdWI0NTBcdWM2Y2NcdWMxMWMgXHVhYzA4IFx1YzIxOCBcdWM1YzZcdWM3M2NcdWJiYzBcdWI4NWMsICgyLCAzKVx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMmE0XHVjNzA0XHVjZTU4XHViMjk0IFx1YjIwNFx1Yjk3YyBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWJiYzBcdWI4NWMgXHViZDg4XHVjNzQ0IFx1YmMxZFx1ZDc5MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzJmXHVjMjE4XHViMjk0IDVcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMTk2NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN3aXRjaGluZyBvbiB0aGUgTGlnaHRzIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiBoYXMgcmVjZW50bHkgYnVpbHQgYW4gZW5vcm1vdXMgYmFybiBjb25zaXN0aW5nIG9mIGFuIFxcKE4gXFx0aW1lcyBOXFwpIGdyaWQgb2Ygcm9vbXMgKFxcKDIgXFxsZXEgTiBcXGxlcSAxMDBcXCkpLCBudW1iZXJlZCBmcm9tIFxcKCgxLDEpXFwpIHVwIHRvIFxcKChOLE4pXFwpLiBCZWluZyBzb21ld2hhdCBhZnJhaWQgb2YgdGhlIGRhcmssIEJlc3NpZSB0aGUgY293IHdhbnRzIHRvIHR1cm4gb24gdGhlIGxpZ2h0cyBpbiBhcyBtYW55IHJvb21zIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5CZXNzaWUgc3RhcnRzIGluIHJvb20gXFwoKDEsMSlcXCksIHRoZSBvbmx5IHJvb20gdGhhdCBpcyBpbml0aWFsbHkgbGl0LiBJbiBzb21lIHJvb21zLCBzaGUgd2lsbCBmaW5kIGxpZ2h0IHN3aXRjaGVzIHRoYXQgc2hlIGNhbiB1c2UgdG8gdG9nZ2xlIHRoZSBsaWdodHMgaW4gb3RoZXIgcm9vbXM7IGZvciBleGFtcGxlIHRoZXJlIG1pZ2h0IGJlIGEgc3dpdGNoIGluIHJvb20gXFwoKDEsMSlcXCkgdGhhdCB0b2dnbGVzIHRoZSBsaWdodHMgaW4gcm9vbSBcXCgoMSwyKVxcKS4gQmVzc2llIGNhbiBvbmx5IHRyYXZlbCB0aHJvdWdoIGxpdCByb29tcywgYW5kIHNoZSBjYW4gb25seSBtb3ZlIGZyb20gYSByb29tIFxcKCh4LHkpXFwpIHRvIGl0cyBmb3VyIGFkamFjZW50IG5laWdoYm9ycyBcXCgoeC0xLHkpXFwpLCBcXCgoeCsxLHkpXFwpLCBcXCgoeCx5LTEpXFwpIGFuZCBcXCgoeCx5KzEpXFwpIChvciBwb3NzaWJseSBmZXdlciBuZWlnaGJvcnMgaWYgdGhpcyByb29tIGlzIG9uIHRoZSBib3VuZGFyeSBvZiB0aGUgZ3JpZCkuPFwvcD5cclxuXHJcbjxwPlBsZWFzZSBkZXRlcm1pbmUgdGhlIG1heGltdW0gbnVtYmVyIG9mIHJvb21zIEJlc3NpZSBjYW4gaWxsdW1pbmF0ZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGludGVnZXJzIFxcKE5cXCkgYW5kIFxcKE1cXCkgKFxcKDEgXFxsZXEgTSBcXGxlcSAyMCwwMDBcXCkpLjxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBcXChNXFwpIGxpbmVzIGVhY2ggZGVzY3JpYmUgYSBzaW5nbGUgbGlnaHQgc3dpdGNoIHdpdGggZm91ciBpbnRlZ2VycyBcXCh4XFwpLCBcXCh5XFwpLCBcXChhXFwpLCBcXChiXFwpLCB0aGF0IGEgc3dpdGNoIGluIHJvb20gXFwoKHgseSlcXCkgY2FuIGJlIHVzZWQgdG8gdG9nZ2xlIHRoZSBsaWdodHMgaW4gcm9vbSBcXCgoYSxiKVxcKS4gTXVsdGlwbGUgc3dpdGNoZXMgbWF5IGV4aXN0IGluIGFueSByb29tLCBhbmQgbXVsdGlwbGUgc3dpdGNoZXMgbWF5IHRvZ2dsZSB0aGUgbGlnaHRzIG9mIGFueSByb29tLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgZ2l2aW5nIHRoZSBtYXhpbXVtIG51bWJlciBvZiByb29tcyBCZXNzaWUgY2FuIGlsbHVtaW5hdGUuPFwvcD5cclxuIiwiaGludCI6IjxwPkhlcmUsIEJlc3NpZSBjYW4gdXNlIHRoZSBzd2l0Y2ggaW4gXFwoKDEsMSlcXCkgdG8gdHVybiBvbiBsaWdodHMgaW4gXFwoKDEsMilcXCkmbmJzcDthbmQgXFwoKDEsMylcXCkuIFNoZSBjYW4gdGhlbiB3YWxrIHRvIFxcKCgxLDMpXFwpIGFuZCB0dXJuIG9uIHRoZSBsaWdodHMgaW4gXFwoKDIsMSlcXCksIGZyb20gd2hpY2ggc2hlIGNhbiB0dXJuIG9uIHRoZSBsaWdodHMgaW4gXFwoKDIsMilcXCkuIFRoZSBzd2l0Y2ggaW4gXFwoKDIsMylcXCkgaXMgaW5hY2Nlc3NpYmxlIHRvIGhlciwgYmVpbmcgaW4gYW4gdW5saXQgcm9vbS4gU2hlIGNhbiB0aGVyZWZvcmUgaWxsdW1pbmF0ZSBhdCBtb3N0IDUgcm9vbXMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=