8342번 - Permutations 다국어

A permutation¹ p of a set m is called an involution if p(p(i)) = i for each i ∈ M.

By a bracket expression of length 2n we mean a word of length 2n consisting only of the characters '(' and ')'. A bracket expression is called correct if the number of opening brackets in the expression equals the number of closing brackets and in every prefix of the expression the number of the characters '(' is no less than the number of characters ')'.

We say that a permutation p of length 2n encodes a bracket expression of length 2n, if opening brackets of the expression (from left to right) are located at positions p(1), p(2), ..., p(n), and closing brackets - also from left to right - at positions p(n+1), p(n+2), ..., p(2n). In particular, in such a case both p(1) < p(2) < ... < p(n) and p(n+1) < p(n+2) < ... < p(2n) hold.

The values of a permutation p for several arguments are known. It should be determined in how many ways the remaining values of p can be determined in such a way that it is an involution and it encodes a correct bracket expression.

¹. A permutation of a set M = {1, 2, 3, ..., m} is any one-to-one function p : M → M.

The first line of the standard input contains two integers n and k (1 ≤ n ≤ 1,000,000, 1 ≤ k ≤ 2n) separated by a single space. Each of the following k lines contains one pair of space-separated integers; the i^th of these lines contains numbers a_i and b_i (1 ≤ a_i, b_i ≤ 2n), meaning that p(a_i) = b_i. All values a_i are distinct and all values b_i are distinct.

The first and only line of the standard output should contain a single integer: the number of permutations of the set {1, 2, 3, ..., 2n} that: are involutions, encode some correct bracket expression, and for which p(a_i) = b_i holds for each 1 ≤ i ≤ k.

The only permutation that complies with requirements of the task is <1, 2, 4, 3, 5, 6>, and it encodes the following bracket expression: (()()).