Living Subgraph

시간 제한1초메모리 제한512 MB

요약

유도 부분 그래프가 연결되어 있고 어떤 한 정점을 지워도 연결 상태가 유지되는 최소 크기의 정점 집합을 찾는다.

난이도: 어려움10점 중 8점
유형: 그래프, BFS, DFS, 그리디
정답자: 아직 제출이 없습니다

문제

이 문제에서는 $|V| = N$ 개의 정점과 $|E| = M$ 개의 간선을 가진 단순 무향 그래프 $G = (V, E)$ 가 주어진다. $G$ 의 유도 부분그래프란 $G$ 의 정점 부분집합과, 양 끝점이 모두 그 부분집합에 속하는 간선들로 이루어진 그래프를 말한다.

$W \subseteq V$ 이고 $G[W]$ 를 정점 집합 $W$ 를 가지는 $G$ 의 유도 부분그래프라 하자. $G[W]$ 가 living subgraph라는 것은 다음 조건을 모두 만족한다는 뜻이다. (1) 정점이 3개 이상이다. (2) 연결되어 있다. (3) 모든 $u \in W$ 에 대해 $G[W \setminus u]$ 가 연결되어 있다. 그래프가 연결되어 있다는 것은 그래프의 임의의 정점에서 모든 정점에 도달할 수 있다는 뜻이다. $W \setminus u$ 는 $W$ 에서 $u$ 를 제거한 집합을 나타낸다.

$G[W]$ 가 living subgraph가 되는 최소 크기의 집합 $W$ 를 찾아, 정점의 개수만 출력하라. $G$ 에 living subgraph가 존재하지 않으면 $-1$ 을 출력한다.

입력

입력의 첫 줄에는 두 정수 $N$ $M$ 이 주어진다. ( $1 \le N \le 20000$ ; $0 \le M \le 20000$ ) $N$ 은 그래프의 정점 수, $M$ 은 간선 수이다. 다음 $M$ 개의 줄에는 각각 두 정수 $u$ $v$ 가 주어진다. ( $1 \le u < v \le N$ ) 이는 정점 $u$ 와 $v$ 를 잇는 간선을 나타낸다. 같은 간선은 주어진 목록에 최대 한 번만 나타난다.

출력

유도 부분그래프가 living subgraph가 되는 최소 정점 수를 한 줄에 출력한다. 주어진 그래프에 living subgraph가 존재하지 않으면 $-1$ 을 출력한다.

예제3

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