시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

In this problem, you are given a simple undirected graph G = (V, E) of |V| = N nodes and |E| = M edges. An induced subgraph of G is defined as a subset of G’s nodes together with any edges whose endpoints are both in the subset.

Let W ⊆ V and G[W] be an induced subgraph of G with W as its nodes. G[W] is a living subgraph if and only if: (1) It contains at least 3 nodes; (2) It is connected; (3) G[W \ u] is connected for all u ∈ W. A graph is connected if and only if all nodes are reachable from any node in the graph. W \ u denotes a set in which u is removed from W.

Your task is to find a set W with the minimum cardinality such that G[W] is a living subgraph; output only the number of nodes. If G does not contain any living subgraph, then output −1.

입력

Input begins with two integers: N M (1 ≤ N ≤ 20000; 0 ≤ M ≤ 20000) representing the number of nodes and edges in the given graph, respectively. The next M lines, each contains two integers: u v (1 ≤ u < v ≤ N) representing an edge connecting node u and v. You may safely assume that each edge appears at most once in the given list.

출력

Output in a line an integer representing the minimum number of nodes in which the induced subgraph is a living subgraph. Output −1 if the given graph contains no living subgraph.

예제 입력 1

5 6
1 2
1 3
1 5
2 3
3 4
4 5

예제 출력 1

3

The induced subgraph G[W] with the set of nodes W = {1, 2, 3} is a living subgraph, and it has the minimum number of nodes.

예제 입력 2

4 3
1 2
1 3
3 4

예제 출력 2

-1

The given graph does not contain any living subgraph.

예제 입력 3

7 8
1 2
1 3
1 6
2 4
2 7
3 5
4 5
5 7

예제 출력 3

4

The induced subgraph G[W] with the set of nodes W = {2, 4, 5, 7} is a living subgraph, and it has the minimum number of nodes.