시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB334584720.000%

문제

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

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

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

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

입력

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

간선의 개수가 2N보다 작거나 같은 그래프만 입력으로 주어진다.

출력

그래프가 선인장이 아니라면 첫째 줄에 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

예제 입력 2

10 2
7 1 2 3 4 5 6 1
6 3 7 8 9 10 2

예제 출력 2

0

예제 입력 3

5 1
4 1 2 3 4

예제 출력 3

0
W3sicHJvYmxlbV9pZCI6IjIxMTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMjBcdWM3NzhcdWM3YTUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjA5OFx1YmIzNCh0cmVlLCBcdWQyYjhcdWI5YWMpXHViNzgwIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWJiMzRcdWQ1YTUgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1Yzc3Y1x1Yzg4NVx1YzczY1x1Yjg1YywgXHViYWE4XHViNGUwIFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM1YjRcdWI1YTQgXHVjMGFjXHVjNzc0XHVkMDc0XHVjNWQwXHViM2M0IFx1YzE4ZFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzc0XHViMmU0LiBcdWM3NzRcdWM2NDAgXHViZTQ0XHVjMmI3XHVkNTU4XHVhYzhjLCBcdWMxMjBcdWM3NzhcdWM3YTVcdWM3NzRcdWI3ODAgXHVjNWYwXHVhY2IwXHViNDFjIFx1YmIzNFx1ZDVhNSBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVjNzdjXHVjODg1XHVjNzNjXHViODVjLCBcdWJhYThcdWI0ZTAgXHVhYzA0XHVjMTIwXHVjNzc0IFx1Y2Q1Y1x1YjMwMCBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1YzBhY1x1Yzc3NFx1ZDA3NFx1YzVkMFx1YjljYyBcdWMxOGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEyMFx1Yzc3OFx1YzdhNVx1YWNmYyBcdWIwOThcdWJiMzRcdWM3NTggXHVjYzI4XHVjNzc0XHVjODEwIFx1YzkxMSBcdWQ1NThcdWIwOThcdWIyOTQsIFx1YzEyMFx1Yzc3OFx1YzdhNVx1Yzc1OCBcdWMyYTRcdWQzMjhcdWIyZGQgXHVjMTFjXHViZTBjXHVhZGY4XHViNzk4XHVkNTA0XHViOTdjIFx1ZDBkZFx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHVjMTIwXHVjNzc4XHVjN2E1XHVjNzc0IFx1YjQxOFx1YjI5NCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNWVjXHViN2ZmIFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQoXHVkMmI4XHViOWFjXHVjNzU4IFx1YzJhNFx1ZDMyOFx1YjJkZCBcdWMxMWNcdWJlMGNcdWQyYjhcdWI5YWNcdWIyOTQgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMCBcdWQ1NWMgXHVhYzFjIFx1YmZkMFx1Yzc3NFx1YjJlNCkuIFx1YzJhNFx1ZDMyOFx1YjJkZCBcdWMxMWNcdWJlMGNcdWFkZjhcdWI3OThcdWQ1MDRcdWI3ODAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWMxMWNcdWJlMGNcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVjNzdjXHVjODg1XHVjNzNjXHViODVjLCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjODEwXHViNGU0XHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxOFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWIyZjlcdWMyZTBcdWM3NDAgXHVjNzc0XHViN2VjXHVkNTVjIFx1YzJhNFx1ZDMyOFx1YjJkZCBcdWMxMWNcdWJlMGNcdWFkZjhcdWI3OThcdWQ1MDQoXHVjNmQwXHViNzk4IFx1YWRmOFx1Yjc5OFx1ZDUwNCBcdWM3OTBcdWMyZTBcdWIzYzQgXHVkM2VjXHVkNTY4KVx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHViODI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBoZWlnaHQ9XCIyMThcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwOFwvY2FjdHVzLlBOR1wiIHdpZHRoPVwiMTg2XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAzNVx1YWMxY1x1Yzc1OCBcdWMyYTRcdWQzMjhcdWIyZGQgXHVjMTFjXHViZTBjXHVhZGY4XHViNzk4XHVkNTA0XHVhYzAwIFx1YzEyMFx1Yzc3OFx1YzdhNVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1Yjc5OFx1ZDUwNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVhZGY4XHViNzk4XHVkNTA0XHVhYzAwIFx1YzEyMFx1Yzc3OFx1YzdhNVx1Yzc3OFx1YzljMCBcdWQzMTBcdWJjYzRcdWQ1NThcdWFjZTAsIFx1YzEyMFx1Yzc3OFx1YzdhNVx1Yzc3NFx1Yjc3Y1x1YmE3NCZuYnNwO1x1YzJhNFx1ZDMyOFx1YjJkZCBcdWMxMWNcdWJlMGNcdWMxMjBcdWM3NzhcdWM3YTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAyMCwwMDApLCBNKDAgJmxlOyBNICZsZTsgMSwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NzQgTlx1YWMxY1x1Yjc3Y1x1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWFjMDRcdWMxMjBcdWI0ZTRcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFjMDRcdWMxMjBcdWI0ZTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWNiZFx1Yjg1Y1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MThcdWIyOTRcdWIzNzAsIE1cdWM3NzQgXHVhZGY4IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgXHVhY2JkXHViODVjXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxYyBcdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM1ZWNcdWI3ZWMgXHVhY2JkXHViODVjXHVjNWQwXHVjMTFjIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NzQgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWIwOThcdWQwYzBcdWIwYTAgXHVjMjE4XHViMjk0IFx1Yzc4OFx1YzljMFx1YjljYywgXHVkNTVjIFx1YWMwNFx1YzEyMFx1Yzc0MCBcdWM3ODVcdWI4MjUgXHVkMzBjXHVjNzdjIFx1YzgwNFx1Y2NiNFx1YzVkMCBcdWI1MzEgXHVkNTVjIFx1YmM4OFx1YjljYyBcdWIwOThcdWQwYzBcdWIwOWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgMk5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWFkZjhcdWI3OThcdWQ1MDRcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVjMTIwXHVjNzc4XHVjN2E1XHVjNzc0IFx1YzU0NFx1YjJjOFx1Yjc3Y1x1YmE3NCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVhY2UwLCBcdWMxMjBcdWM3NzhcdWM3YTVcdWM3NzRcdWI3N2NcdWJhNzQgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCZuYnNwO1x1YzJhNFx1ZDMyOFx1YjJkZCBcdWMxMWNcdWJlMGNcdWMxMjBcdWM3NzhcdWM3YTVcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMTExIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2FjdHVzIFJlbG9hZGVkIiwiZGVzY3JpcHRpb24iOiI8cD5DYWN0dXMgaXMgYSBjb25uZWN0ZWQgdW5kaXJlY3RlZCBncmFwaCBpbiB3aGljaCBldmVyeSBlZGdlIGxpZXMgb24gYXQgbW9zdCBvbmUgc2ltcGxlIGN5Y2xlLiBJbnR1aXRpdmVseSBjYWN0dXMgaXMgYSBnZW5lcmFsaXphdGlvbiBvZiBhIHRyZWUgd2hlcmUgc29tZSBjeWNsZXMgYXJlIGFsbG93ZWQuIFlvdXIgdGFzayBmaXJzdCBpcyB0byB2ZXJpZnkgaWYgdGhlIGdpdmVuIGdyYXBoIGlzIGEgY2FjdHVzIG9yIG5vdC4gSW1wb3J0YW50IGRpXHVmYjAwZXJlbmNlIGJldHdlZW4gYSBjYWN0dXMgYW5kIGEgdHJlZSBpcyB0aGF0IGEgY2FjdHVzIGNhbiBoYXZlIGEgbnVtYmVyIG9mIHNwYW5uaW5nIHN1YmdyYXBocyB0aGF0IGFyZSBhbHNvIGNhY3R1c2VzLiBUaGUgbnVtYmVyIG9mIHN1Y2ggc3ViZ3JhcGhzIChpbmNsdWRpbmcgdGhlIGdyYXBoIGl0c2VsZikgZGV0ZXJtaW5lcyBjYWN0dXNuZXNzIG9mIGEgZ3JhcGggKHRoaXMgbnVtYmVyIGlzIG9uZSBmb3IgYSBjYWN0dXMgdGhhdCBpcyBqdXN0IGEgdHJlZSkuIFRoZSBjYWN0dXNuZXNzIG9mIGEgZ3JhcGggdGhhdCBpcyBub3QgYSBjYWN0dXMgaXMgY29uc2lkZXJlZCB0byBiZSB6ZXJvLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NhY3R1cy5wbmdcIiBzdHlsZT1cImhlaWdodDoyNTVweDsgd2lkdGg6NTYzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IGdyYXBoIG9uIHRoZSBwaWN0dXJlIGlzIGEgY2FjdHVzIHdpdGggY2FjdHVzbmVzcyAzNS4gVGhlIHNlY29uZCBncmFwaCBpcyBub3QgYSBjYWN0dXMgYmVjYXVzZSBlZGdlICgyLCAzKSBsaWVzIG9uIHR3byBjeWNsZXMuIFRoZSB0aGlyZCBncmFwaCBpcyBub3QgYSBjYWN0dXMgYmVjYXVzZSBpdCBpcyBub3QgY29ubmVjdGVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbnMgdHdvIGludGVnZXIgbnVtYmVycyBuIGFuZCBtICgxICZsZTsgbiAmbGU7IDIwMDAwLCAwICZsZTsgbSAmbGU7IDEwMDApLiBIZXJlIG4gaXMgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBpbiB0aGUgZ3JhcGguIFZlcnRpY2VzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbi4gRWRnZXMgb2YgdGhlIGdyYXBoIGFyZSByZXByZXNlbnRlZCBieSBhIHNldCBvZiBlZGdlLWRpc3RpbmN0IHBhdGhzLCB3aGVyZSBtIGlzIHRoZSBudW1iZXIgb2Ygc3VjaCBwYXRocy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIG0gbGluZXMgY29udGFpbnMgYSBwYXRoIGluIHRoZSBncmFwaC4gQSBwYXRoIHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgbnVtYmVyIGs8c3ViPmk8XC9zdWI+ICgyICZsZTsgazxzdWI+aTxcL3N1Yj4gJmxlOyAxMDAwKSBmb2xsb3dlZCBieSBrPHN1Yj5pPFwvc3ViPiBpbnRlZ2VycyBmcm9tIDEgdG8gbi4gVGhlc2UgazxzdWI+aTxcL3N1Yj4gaW50ZWdlcnMgcmVwcmVzZW50IHZlcnRpY2VzIG9mIGEgcGF0aC4gUGF0aCBjYW4gZ28gdG8gdGhlIHNhbWUgdmVydGV4IG11bHRpcGxlIHRpbWVzLCBidXQgZXZlcnkgZWRnZSBpcyB0cmF2ZXJzZWQgZXhhY3RseSBvbmNlIGluIHRoZSB3aG9sZSBpbnB1dCBmaWxlLiBUaGVyZSBhcmUgbm8gbXVsdGllZGdlcyBpbiB0aGUgZ3JhcGggKHRoZXJlIGlzIGF0IG1vc3Qgb25lIGVkZ2UgYmV0d2VlbiBhbnkgdHdvIHZlcnRpY2VzKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Xcml0ZSB0byB0aGUgb3V0cHV0IGZpbGUgYSBzaW5nbGUgaW50ZWdlciBudW1iZXIgJm1kYXNoOyB0aGUgY2FjdHVzbmVzcyBvZiB0aGUgZ2l2ZW4gZ3JhcGguIE5vdGUgdGhhdCBjYWN0dXNuZXNzIGNhbiBiZSBxdWl0ZSBhIGxhcmdlIG51bWJlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d