Informatica Online Judge

  Spanning Cactus [1285 / 0505]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 2   Total Tried : 53


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

트리(Tree, 나무)란 연결된 무향 그래프의 일종으로, 모든 간선이 어떤 사이클에도 속하지 않는 그래프이다.

이와 유사하게, 캑터스(Cactus, 선인장)란 연결된 무향 그래프의 일종으로, 모든 간선이 최대 한 개의 사이클에만 속할 수 있는 그래프이다.

스패닝 그래프(Spanning Graph)란 주어진 그래프의 서브 그래프의 일종으로, 모든 정점들이 연결되는 경우를 의미한다. 물론 자기 자신도 하나의 스패닝 그래프이다.

Tree의 스패닝 그래프는 오직 하나만 존재한다.

Cactus와 Tree의 차이점 중 하나는, Cactus의 스패닝 그래프를 택했을 때 Cactus가 되는 경우가 여럿 있다는 것이다.

스패닝 그래프 중 Spanning Tree와 Spanning Cactus를 따로 볼 수 있다.

Spanning Tree는 서브그래프들 중 Tree가 되는 것을 말하고, Spanning Cactus는 서브그래프 중 Cactus가 되는 것을 말한다.




예를 들어, 위와 같은 그래프의 경우는 Cactus이다. 이 그래프의 Spanning Cactus는 서로 다른 35가지가 존재할 수 있다.

(Spanning Tree는 Spanning Cactus의 한 종류이다.)

Cactus가 주어졌을 때, Spanning Cactus의 개수를 구해내는 프로그램을 작성하시오.

Input

첫째 줄에 두 정수 N, M이 주어진다.

이는 그래프의 정점이 N개라는 의미이다.

선인장의 간선들은 서로 다른 간선들로 이루어진 경로로 표현되는데, M이 그 경로의 개수이다.

각 줄의 첫 번째 정수는 경로에 포함된 정점의 개수이다.

여러 경로에서 하나의 정점이 여러 번 나타날 수는 있지만, 한 간선은 입력 파일 전체에 딱 한 번만 나타난다.

[입력값의 정의역]
1 ≤ N ≤ 20,000
0 ≤ M ≤ 1,000

Output

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

IO Example

입력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
5 1
4 1 2 3 4

출력2
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]