Unidirectional Link Network

A multicomputer system consists of several nodes, each with its own memory. The nodes are connected to one another by unidirectional communication links, so the interconnection network can be described as a directed graph: vertices are nodes and edges are the unidirectional links.

The two most important structures in an interconnection network are the linear array and the ring.

• A linear array places nodes in order $0, 1, \dots, k-1$ such that, for every $0 \le i < k-1$, there is a unidirectional link from node $i$ to node $i+1$. A linear array may consist of a single node.
• A ring is a linear array with one additional unidirectional link from node $k-1$ back to node $0$.

To support parallel applications, the whole system must be decomposed into several subsystems. Each subsystem must be a ring or a linear array, and no two subsystems may share a node.

A ring of $k$ nodes is worth $k$ dollars, and a linear array of $k$ nodes is worth $k-1$ dollars. Consequently a linear array of a single node is worth $0$ dollars.

Given an interconnection network, write a program that decomposes the system into rings and/or linear arrays so that the total value is maximized.

For example, decomposing a network into a ring of 6 nodes and a linear array of 8 nodes gives a total value of $6 + 7 = 13$ dollars, which can be the maximum possible value.

The first line contains the number of test cases $T$. For each test case, the first line contains the number of nodes $n$ and the number of unidirectional links $m$ ($n \le 1{,}000$, $m \le 50{,}000$). Nodes are numbered from $0$ to $n-1$. Each of the next $m$ lines contains two integers $u$ and $v$, separated by a space, denoting a unidirectional link from node $u$ to node $v$.

For each test case, print a single line containing one integer: the maximum total value obtainable by decomposing the given interconnection network into rings and/or linear arrays.