Good Bye 2021: 2022 is NEAR |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dfs and similar

dp

graphs

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Just Add an Edge

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

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.

Example

Input

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

Output

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$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/18/2024 12:47:23 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|