선인장 간선 옮기기

선인장은 모든 간선이 많아야 하나의 단순 사이클에만 속하는 연결 무향 그래프다. 트리에 사이클을 조금 허용한 그래프라고 보면 된다. 선인장에는 같은 두 정점을 잇는 다중 간선이 없고, 자기 자신으로 돌아오는 루프도 없다.

선인장이 하나 주어진다. 간선을 옮긴다는 것은 그래프에서 간선 하나를 지우고, 대신 다른 두 정점을 잇는 간선 하나를 넣는 것이다. 옮긴 뒤의 그래프도 선인장이어야 한다. 간선을 옮기는 방법이 몇 가지인지 구하여라.

지운 간선이 다르거나 넣은 간선이 다르면 서로 다른 방법으로 센다. 넣는 간선의 두 끝점은 지운 간선의 두 끝점과 같은 쌍일 수 없다.

위 그림은 선인장의 예 두 개다.

첫째 줄에 정점의 개수 $n$과 경로의 개수 $m$이 주어진다 ($1 \le n \le 50000$, $0 \le m \le 50000$). 정점은 $1$번부터 $n$번까지 번호가 붙어 있다. 그래프의 간선은 서로 같은 간선을 두 번 쓰지 않는 경로 $m$개로 주어진다.

다음 $m$개 줄에는 경로가 하나씩 주어진다. 각 줄은 정수 $k_i$ ($2 \le k_i \le 1000$)로 시작하고, 그 뒤에 $1$ 이상 $n$ 이하인 정수 $k_i$개가 이어진다. 이 수들은 경로가 지나는 정점을 순서대로 나타낸다. 경로에서 이웃한 두 정점은 서로 다르다. 한 경로가 같은 정점을 여러 번 지날 수 있지만, 그래프의 각 간선은 입력 전체에서 정확히 한 번만 나온다.

주어지는 그래프는 선인장이다.

간선을 옮기는 방법의 수를 정수 하나로 출력한다.