Strange Trees

After learning tree structures, Mingming became fascinated with strange trees. In this problem, you are given N vertices labeled from 1 to N and the final degrees for some of these vertices. You are allowed to connect any two vertices with an edge. Your task is to count how many distinct trees (i.e. connected acyclic graphs) can be formed such that for each vertex with a specified degree requirement, its degree in the tree is exactly as given.

Recall that a tree on N vertices has exactly N - 1 edges and by the Prüfer code, the degree of vertex i is equal to the number of times i appears in the Prüfer sequence plus one. Thus if a vertex i is specified to have degree \(d_i\), then it must appear exactly \(d_i - 1\) times in the Prüfer code. The remaining vertices (with no restrictions) can appear arbitrarily. The total length of the Prüfer sequence is \(N-2\), so if we denote by \(S = \sum_{\text{specified } i}(d_i - 1)\) then the remaining positions that can be arbitrarily chosen is \(k = N-2 - S\), and these positions can be filled by any of the \(N-M\) unspecified vertices. Therefore, the number of valid trees is given by:

[ \text{Answer} = \frac{(N-2)!}{\prod_{\text{specified } i}(d_i-1)!} \times (N-M)^k, \quad \text{where } k = N-2 - \sum_{\text{specified } i}(d_i-1). ]

If \(k < 0\) or any specified degree is less than 1, then no valid tree exists, and the answer is 0.

inputFormat

The first line contains two integers N and M where \(1 \leq N \leq 10^5\) (or a lower limit in practice for this problem) and \(0 \leq M \leq N\) is the number of vertices with a specified degree.

Each of the following M lines contains two integers u and d indicating that vertex u (\(1 \leq u \leq N\)) must have degree d (with \(d \ge 1\)).

If \(M = 0\), then no vertex has a specified degree.

outputFormat

Output a single integer which is the number of trees satisfying the degree requirements. If no valid tree exists, output 0.

sample

4 2
1 2
4 1

4