A14682. Just Add an Edge

You are given a directed acyclic graph with $n$ vertices and $m$ edges. For all edges $a \to b$ in the graph, $a < b$ holds.

You need to find the number of pairs of vertices $x$ , $y$ , such that $x > y$ and after adding the edge $x \to y$ to the graph, it has a Hamiltonian path.

The first line of input contains one integer $t$ ( $1 \leq t \leq 5$ ): the number of test cases.

The next lines contains the descriptions of the test cases.

In the first line you are given two integers $n$ and $m$ ( $1 \leq n \leq 150\,000$ , $0 \leq m \leq \min(150\,000, \frac{n(n-1)}{2})$ ): the number of vertices and edges in the graph.

Each of the next $m$ lines contains two integers $a$ , $b$ ( $1 \leq a < b \leq n$ ), specifying an edge $a \to b$ in the graph. No edge $a \to b$ appears more than once.

For each test case, print one integer: the number of pairs of vertices $x$ , $y$ , $x > y$ , such that after adding the edge $x \to y$ to the graph, it has a Hamiltonian path.

In the first example, any edge $x \to y$ such that $x > y$ is valid, because there already is a path $1 \to 2 \to 3$ .

In the second example only the edge $4 \to 1$ is valid. There is a path $3 \to 4 \to 1 \to 2$ if this edge is added.

In the third example you can add edges $2 \to 1$ , $3 \to 1$ , $4 \to 1$ , $4 \to 2$ .