선인장 그래프

무방향 그래프가 주어진다. 이 그래프에 들어 있는 서로 다른 단순 사이클(같은 정점을 두 번 지나지 않는 사이클)의 개수를 세는 것이 목표다.

단, 대상 그래프는 개수를 세기 쉬운 형태로 제한한다. 서로 다른 두 사이클이 공통으로 가지는 정점이 최대 한 개인 그래프만 다룬다. 이런 그래프를 선인장(cactus) 그래프라고 부른다.

각 그래프에 대해, 그래프가 이 조건을 만족하면 단순 사이클의 개수를 출력하고, 조건을 만족하지 않으면 세기를 거부한다는 뜻으로 NIE를 출력한다. (NIE는 폴란드어로 '아니오'를 뜻한다.)

첫째 줄에 데이터 집합의 개수 $L$이 주어진다.

각 데이터 집합의 첫째 줄에는 그래프의 정점 수 $N$과 간선 수 $M$이 주어진다 ($1 \le N, M \le 10^6$). 이어지는 $M$개의 줄에는 각 간선이 잇는 두 정점 $A$와 $B$가 주어진다. $A$와 $B$는 서로 다르며, 정점 번호는 $0$부터 시작한다. 같은 간선이 두 번 주어지는 경우는 없다.

각 데이터 집합마다 한 줄에 결과를 하나씩 출력한다. 그래프가 조건(서로 다른 두 사이클이 공통 정점을 최대 한 개만 가진다)을 만족하면 단순 사이클의 개수를, 그렇지 않으면 NIE를 출력한다.