Andi has a network $G$ with $N$ machines and $M$ links; each link connects exactly two different machines. Due to some circumstances, Andi has to make his network "complete", i.e. every machine is directly linked to every other machine. This means Andy has to add a new link between any pair of machines which are not already directly linked.
In order to accomplish his goal, Andi outsources the work to a company, Go. Go accepts any work order on a network $G$ with a requested integer $k$, i.e. $g o (G, k)$. The way Go works: First, it creates a list $L$ containing *all* pair of machines which are *not* yet directly linked. Then, Go evaluates each pair of machines $(a, b)$ from $L$ and create a new link between them if $delta_a + delta_b >= k$. Note that $delta_a$ is the degree of machine $a$, i.e. the number of links $a$ has at the time of evaluation. Similarly, $delta_b$ is for machine $b$.
The problem with Go's procedure is it evaluates each pair of machines in the order appeared in $L$. For example, let $G$ be a network with $N = 4$ machines (machine $1$, $2$, $3$, and $4$) and $M = 3$ links; the links are ${(1, 2), (2, 3), (3, 4)}$. The degree of each machine before a work order is requested is: $delta_1 = 1$, $delta_2 = 2$, $delta_3 = 2$, $delta_4 = 1$, or simply can be written as $[ 1, 2, 2, 1 ]$. Let say a work order with $k = 3$ is requested ($g o (G, 3)$).
Consider these two lists:
Ordering a work to Go can be very expensive with lower $k$, thus, Andi has to make $k$ as high as possible while maintaining the possibility that a complete network can be achieved with $k$. In other words, Andi wants the highest $k$ such that there exists $L$ such that $g o (G, k)$ can produce a complete network, and for any $j$ ($j > k$), there is no valid $L$ for $g o (G, j)$ which can produce a complete network. Your task in this problem is to find such $k$.
Input begins with a line containing two integers: $N$ $M$ ($2 <= N <= 500$; $0 <= M < frac(N times (N -1), 2)$) representing the number of machines and the number existing links, respectively. The machines are numbered from $1$ to $N$. The next $M$ lines, each contains two integers: $a_i$ $b_i$ ($1 <= a_i < b_i <= N$) representing an existing link connecting machine $a_i$ and $b_i$. You are guaranteed that each pair $(a_i, b_i)$ will appear at most once in the input.
Output contains an integer $k$ in a line, as requested.
_Explanation for the sample input/output #2_
Andi's network has no link at all at the beginning. To make his network complete, Andi has to order $g o (G, 0)$.
## Input
Input begins with a line containing two integers: $N$ $M$ ($2 <= N <= 500$; $0 <= M < frac(N times (N -1), 2)$) representing the number of machines and the number existing links, respectively. The machines are numbered from $1$ to $N$. The next $M$ lines, each contains two integers: $a_i$ $b_i$ ($1 <= a_i < b_i <= N$) representing an existing link connecting machine $a_i$ and $b_i$. You are guaranteed that each pair $(a_i, b_i)$ will appear at most once in the input.
## Output
Output contains an integer $k$ in a line, as requested.
[samples]
## Note
_Explanation for the sample input/output #2_Andi's network has no link at all at the beginning. To make his network complete, Andi has to order $g o (G, 0)$.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n_k \in \mathbb{Z} $ denote the number of nodes.
- Let $ \mathbf{a}_k = (a_{k,1}, \dots, a_{k,n_k}) \in \mathbb{Z}_{\geq 0}^{n_k} $ be the initial in-degrees of nodes $ 1 $ to $ n_k $.
- Let $ \mathbf{b}_k = (b_{k,1}, \dots, b_{k,n_k}) \in \mathbb{Z}_{\geq 0}^{n_k} $ be the final in-degrees of nodes $ 1 $ to $ n_k $, with $ 0 \leq b_{k,i} \leq a_{k,i} $ for all $ i $.
**Constraints**
1. $ 1 \leq T \leq 370 $
2. $ 1 \leq n_k \leq 2 \times 10^5 $ for each $ k $
3. $ 0 \leq a_{k,i} < n_k $, $ 0 \leq b_{k,i} \leq a_{k,i} $ for all $ i \in \{1, \dots, n_k\} $
4. $ \sum_{k=1}^T n_k \leq 2 \times 10^6 $
5. $ \sum_{k=1}^T \sum_{i=1}^{n_k} a_{k,i} \leq 2 \times 10^6 $
6. The graph must have no self-loops and no repeated edges.
**Objective**
For each test case $ k $:
- If no directed graph exists satisfying the in-degree conditions (initial $ \mathbf{a}_k $, final $ \mathbf{b}_k $), output $ -1 $.
- Otherwise, output:
- The number of edges $ m_k = \sum_{i=1}^{n_k} (a_{k,i} - b_{k,i}) $,
- Then $ m_k $ directed edges $ (u, v) $ with $ 1 \leq u, v \leq n_k $, $ u \ne v $, no repeated edges, such that:
- The in-degree of node $ i $ in the final graph is $ b_{k,i} $,
- The in-degree of node $ i $ in the full graph (before removal) is $ a_{k,i} $,
- The removed edges form a set of $ \sum_{i=1}^{n_k} (a_{k,i} - b_{k,i}) $ edges whose removal results in the final in-degrees $ \mathbf{b}_k $.
Equivalently: Construct a directed graph with $ n_k $ nodes and $ \sum_{i=1}^{n_k} a_{k,i} $ edges (no self-loops, no repeats), such that after removing exactly $ a_{k,i} - b_{k,i} $ incoming edges from each node $ i $, the resulting graph has in-degrees $ \mathbf{b}_k $.