시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 37 6 6 26.087%

문제

나무(tree, 트리)란 연결된 무향 그래프의 일종으로, 모든 간선이 어떤 사이클에도 속하지 않는 그래프이다. 이와 비슷하게, 선인장이란 연결된 무향 그래프의 일종으로, 모든 간선이 최대 한 개의 사이클에만 속할 수 있는 그래프이다.

선인장과 나무의 차이점 중 하나는, 선인장의 스패닝 서브그래프를 택했을 때 선인장이 되는 경우가 여럿 있다는 것이다(트리의 스패닝 서브트리는 자기 자신 한 개 뿐이다). 스패닝 서브그래프란 주어진 그래프의 서브그래프의 일종으로, 모든 정점들이 연결되는 경우를 의미한다. 당신은 이러한 스패닝 서브그래프(원래 그래프 자신도 포함)의 개수를 알아내려 한다.

예를 들어, 위와 같은 그래프의 경우에는 35개의 스패닝 서브그래프가 선인장이 된다.

선인장이 주어졌을 때, 스패닝 서브선인장의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N(1≤N≤20,000), M(0≤M≤1,000)이 주어진다. 이는 그래프의 정점이 N개라는 의미이다. 선인장의 간선들은 서로 다른 간선들로 이루어진 경로로 표현되는데, M이 그 경로의 개수이다. 각 줄의 첫 번째 정수는 경로에 포함된 정점의 개수이다. 여러 경로에서 하나의 정점이 여러 번 나타날 수는 있지만, 한 간선은 입력 파일 전체에 딱 한 번만 나타난다.

출력

첫째 줄에 답을 출력한다. 만약 선인장이 아닌 경우에는 0을 출력한다.

예제 입력 1

14 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
2 2 14

예제 출력 1

35
W3sicHJvYmxlbV9pZCI6IjIxMTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMjBcdWM3NzhcdWM3YTUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjA5OFx1YmIzNCh0cmVlLCBcdWQyYjhcdWI5YWMpXHViNzgwIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWJiMzRcdWQ1YTUgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1Yzc3Y1x1Yzg4NVx1YzczY1x1Yjg1YywgXHViYWE4XHViNGUwIFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM1YjRcdWI1YTQgXHVjMGFjXHVjNzc0XHVkMDc0XHVjNWQwXHViM2M0IFx1YzE4ZFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzc0XHViMmU0LiBcdWM3NzRcdWM2NDAgXHViZTQ0XHVjMmI3XHVkNTU4XHVhYzhjLCBcdWMxMjBcdWM3NzhcdWM3YTVcdWM3NzRcdWI3ODAgXHVjNWYwXHVhY2IwXHViNDFjIFx1YmIzNFx1ZDVhNSBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVjNzdjXHVjODg1XHVjNzNjXHViODVjLCBcdWJhYThcdWI0ZTAgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Y2Q1Y1x1YjMwMCBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1YzBhY1x1Yzc3NFx1ZDA3NFx1YzVkMFx1YjljYyBcdWMxOGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+XHVjMTIwXHVjNzc4XHVjN2E1XHVhY2ZjIFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWM4MTAgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjI5NCwgXHVjMTIwXHVjNzc4XHVjN2E1XHVjNzU4IFx1YzJhNFx1ZDMyOFx1YjJkZCBcdWMxMWNcdWJlMGNcdWFkZjhcdWI3OThcdWQ1MDRcdWI5N2MgXHVkMGRkXHVkNTg4XHVjNzQ0IFx1YjU0YyBcdWMxMjBcdWM3NzhcdWM3YTVcdWM3NzQgXHViNDE4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM1ZWNcdWI3ZmYgXHVjNzg4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNChcdWQyYjhcdWI5YWNcdWM3NTggXHVjMmE0XHVkMzI4XHViMmRkIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1YjI5NCBcdWM3OTBcdWFlMzAgXHVjNzkwXHVjMmUwIFx1ZDU1YyBcdWFjMWMgXHViZmQwXHVjNzc0XHViMmU0KS4gXHVjMmE0XHVkMzI4XHViMmRkIFx1YzExY1x1YmUwY1x1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjc4MCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YzExY1x1YmUwY1x1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWM3N2NcdWM4ODVcdWM3M2NcdWI4NWMsIFx1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTBcdWI0ZTRcdWM3NzQgXHVjNWYwXHVhY2IwXHViNDE4XHViMjk0IFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMmE0XHVkMzI4XHViMmRkIFx1YzExY1x1YmUwY1x1YWRmOFx1Yjc5OFx1ZDUwNChcdWM2ZDBcdWI3OTggXHVhZGY4XHViNzk4XHVkNTA0IFx1Yzc5MFx1YzJlMFx1YjNjNCBcdWQzZWNcdWQ1NjgpXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWIwYjRcdWI4MjQgXHVkNTVjXHViMmU0LjxcL3A+XHJcbjxwPjxpbWcgd2lkdGg9XCIxODZcIiBoZWlnaHQ9XCIyMThcIiBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwOFwvY2FjdHVzLlBOR1wiIFwvPjxcL3A+XHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAzNVx1YWMxY1x1Yzc1OCBcdWMyYTRcdWQzMjhcdWIyZGQgXHVjMTFjXHViZTBjXHVhZGY4XHViNzk4XHVkNTA0XHVhYzAwIFx1YzEyMFx1Yzc3OFx1YzdhNVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuPHA+XHVjMTIwXHVjNzc4XHVjN2E1XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzJhNFx1ZDMyOFx1YjJkZCBcdWMxMWNcdWJlMGNcdWMxMjBcdWM3NzhcdWM3YTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggTigxJmxlO04mbGU7MjAsMDAwKSwgTSgwJmxlO00mbGU7MSwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NzQgTlx1YWMxY1x1Yjc3Y1x1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuIFx1YzEyMFx1Yzc3OFx1YzdhNVx1Yzc1OCBcdWFjMDRcdWMxMjBcdWI0ZTRcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFjMDRcdWMxMjBcdWI0ZTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWNiZFx1Yjg1Y1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MThcdWIyOTRcdWIzNzAsIE1cdWM3NzQgXHVhZGY4IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgXHVhY2JkXHViODVjXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxYyBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM1ZWNcdWI3ZWMgXHVhY2JkXHViODVjXHVjNWQwXHVjMTFjIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NzQgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWIwOThcdWQwYzBcdWIwYTAgXHVjMjE4XHViMjk0IFx1Yzc4OFx1YzljMFx1YjljYywgXHVkNTVjIFx1YWMwNFx1YzEyMFx1Yzc0MCBcdWM3ODVcdWI4MjUgXHVkMzBjXHVjNzdjIFx1YzgwNFx1Y2NiNFx1YzVkMCBcdWI1MzEgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWIwOThcdWQwYzBcdWIwOWNcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWMxMjBcdWM3NzhcdWM3YTVcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIxMTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDYWN0dXMgUmVsb2FkZWQiLCJkZXNjcmlwdGlvbiI6IjxwPkNhY3R1cyBpcyBhIGNvbm5lY3RlZCB1bmRpcmVjdGVkIGdyYXBoIGluIHdoaWNoIGV2ZXJ5IGVkZ2UgbGllcyBvbiBhdCBtb3N0IG9uZSBzaW1wbGUgY3ljbGUuIEludHVpdGl2ZWx5IGNhY3R1cyBpcyBhIGdlbmVyYWxpemF0aW9uIG9mIGEgdHJlZSB3aGVyZSBzb21lIGN5Y2xlcyBhcmUgYWxsb3dlZC4gWW91ciB0YXNrIGZpcnN0IGlzIHRvIHZlcmlmeSBpZiB0aGUgZ2l2ZW4gZ3JhcGggaXMgYSBjYWN0dXMgb3Igbm90LiBJbXBvcnRhbnQgZGlcdWZiMDBlcmVuY2UgYmV0d2VlbiBhIGNhY3R1cyBhbmQgYSB0cmVlIGlzIHRoYXQgYSBjYWN0dXMgY2FuIGhhdmUgYSBudW1iZXIgb2Ygc3Bhbm5pbmcgc3ViZ3JhcGhzIHRoYXQgYXJlIGFsc28gY2FjdHVzZXMuIFRoZSBudW1iZXIgb2Ygc3VjaCBzdWJncmFwaHMgKGluY2x1ZGluZyB0aGUgZ3JhcGggaXRzZWxmKSBkZXRlcm1pbmVzIGNhY3R1c25lc3Mgb2YgYSBncmFwaCAodGhpcyBudW1iZXIgaXMgb25lIGZvciBhIGNhY3R1cyB0aGF0IGlzIGp1c3QgYSB0cmVlKS4gVGhlIGNhY3R1c25lc3Mgb2YgYSBncmFwaCB0aGF0IGlzIG5vdCBhIGNhY3R1cyBpcyBjb25zaWRlcmVkIHRvIGJlIHplcm8uPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2FjdHVzLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI1NXB4OyB3aWR0aDo1NjNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgZmlyc3QgZ3JhcGggb24gdGhlIHBpY3R1cmUgaXMgYSBjYWN0dXMgd2l0aCBjYWN0dXNuZXNzIDM1LiBUaGUgc2Vjb25kIGdyYXBoIGlzIG5vdCBhIGNhY3R1cyBiZWNhdXNlIGVkZ2UgKDIsIDMpIGxpZXMgb24gdHdvIGN5Y2xlcy4gVGhlIHRoaXJkIGdyYXBoIGlzIG5vdCBhIGNhY3R1cyBiZWNhdXNlIGl0IGlzIG5vdCBjb25uZWN0ZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBjb250YWlucyB0d28gaW50ZWdlciBudW1iZXJzIG4gYW5kIG0gKDEgJmxlOyBuICZsZTsgMjAwMDAsIDAgJmxlOyBtICZsZTsgMTAwMCkuIEhlcmUgbiBpcyB0aGUgbnVtYmVyIG9mIHZlcnRpY2VzIGluIHRoZSBncmFwaC4gVmVydGljZXMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBuLiBFZGdlcyBvZiB0aGUgZ3JhcGggYXJlIHJlcHJlc2VudGVkIGJ5IGEgc2V0IG9mIGVkZ2UtZGlzdGluY3QgcGF0aHMsIHdoZXJlIG0gaXMgdGhlIG51bWJlciBvZiBzdWNoIHBhdGhzLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgbSBsaW5lcyBjb250YWlucyBhIHBhdGggaW4gdGhlIGdyYXBoLiBBIHBhdGggc3RhcnRzIHdpdGggYW4gaW50ZWdlciBudW1iZXIgazxzdWI+aTxcL3N1Yj4gKDIgJmxlOyBrPHN1Yj5pPFwvc3ViPiAmbGU7IDEwMDApIGZvbGxvd2VkIGJ5IGs8c3ViPmk8XC9zdWI+IGludGVnZXJzIGZyb20gMSB0byBuLiBUaGVzZSBrPHN1Yj5pPFwvc3ViPiBpbnRlZ2VycyByZXByZXNlbnQgdmVydGljZXMgb2YgYSBwYXRoLiBQYXRoIGNhbiBnbyB0byB0aGUgc2FtZSB2ZXJ0ZXggbXVsdGlwbGUgdGltZXMsIGJ1dCBldmVyeSBlZGdlIGlzIHRyYXZlcnNlZCBleGFjdGx5IG9uY2UgaW4gdGhlIHdob2xlIGlucHV0IGZpbGUuIFRoZXJlIGFyZSBubyBtdWx0aWVkZ2VzIGluIHRoZSBncmFwaCAodGhlcmUgaXMgYXQgbW9zdCBvbmUgZWRnZSBiZXR3ZWVuIGFueSB0d28gdmVydGljZXMpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPldyaXRlIHRvIHRoZSBvdXRwdXQgZmlsZSBhIHNpbmdsZSBpbnRlZ2VyIG51bWJlciAmbWRhc2g7IHRoZSBjYWN0dXNuZXNzIG9mIHRoZSBnaXZlbiBncmFwaC4gTm90ZSB0aGF0IGNhY3R1c25lc3MgY2FuIGJlIHF1aXRlIGEgbGFyZ2UgbnVtYmVyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==