선인장 그래프

시간 제한5초메모리 제한128 MB

요약

무향 그래프의 단순 사이클 개수를 세고 두 사이클이 정점 둘 이상을 공유하면 NIE를 출력합니다.

난이도: 보통10점 중 7점
유형: DFS, 그래프
정답자: 아직 제출이 없습니다

문제

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

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

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

입력

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

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

출력

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

예제5

예제 1

입력

예상 출력

NIE
0

예제 2
입력
```
1
3 3
0 1
1 2
2 0
```
예상 출력
```
1
```
예제 3
입력
```
1
5 6
0 1
1 2
2 0
2 3
3 4
4 2
```
예상 출력
```
2
```
예제 4
입력
```
1
6 7
0 1
1 2
2 0
2 3
3 4
4 5
5 3
```
예상 출력
```
2
```
예제 5
입력
```
1
4 3
0 1
1 2
2 3
```
예상 출력
```
0
```