(Solved): fg There are N Rubrik nodes numbered 1,2,N on a Rubrik Cluster. And these are connected with some ...

There are $N$ Rubrik nodes numbered $1,2,\dots N$ on a Rubrik Cluster. And these are connected with some bidirectional connections. Every connection connects two distinct nodes. Also, for any two nodes, there is at most one connection that connects them directly. Sometimes we need to partition these nodes into 2 parts for even load distribution for recovering data and hence we need to divide the number of nodes into two partitions - partition $\mathbf{X}$ and partition $\mathbf{Y}$. After partition every node should be part of either partition $X$ or partition $Y$ and it is allowed for all the nodes to be part of a single partition. The condition that should be satisfied for all the partitioned nodes is that - Any two nodes in the same partition should be directly connected by a connection Find the minimum possible number of connections whose endpoint nodes belong the same pattition. If it is impossible to divide the cities into partition $X$ and partition $Y$ so that the condition is satisfied, print -1 . Constraints $\begin{array}{l}2?N?700\\ 0?M?N(N?1)/2\\ 1?A_i?N\\ 1?B_i?N\\ A_i?=B_i\end{array}$ If $i?=j$, at least one of the following holds: $A_i?=A_j$ and $B_i?=B_j$. If $i?=j$, at least one of the following holds: $A_i?=B_j$ and $B_i?=A_j$. Input Input is glveri from standard inpur in the following format: $\begin{array}{ll}N& M\\ A_1& B_1\\ A_2& B_2\\ ?& \\ A_M& B_M\end{array}$ Output Print the answer. Sample linput $\begin{array}{l}55\\ 12\\ 13\\ 34\\ 35\\ 45\end{array}$ Sample Output $4$ For example, if the nodes 1,2 belong to partition $x$ and the nodes $3,4,5$ belong to partition $Y$. and the condition is sartisfied. Here, the number of connections whose endpoint nodes belong to the same partition is 4 . Sample Input 51 12 Sample Output $?1$