codeforces#P1616G. Just Add an Edge
Just Add an Edge
Description
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.
Input
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.
Output
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.
Samples
3
3 2
1 2
2 3
4 3
1 2
3 4
1 4
4 4
1 3
1 4
2 3
3 4
3
1
4
Note
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$.