×

计蒜客

  1. 题库
  2. The Maximum Unreachable Node Set
  3. 问答
  • 41.53%
  • 262144K

In this problem, we would like to talk about unreachable sets of a directed acyclic graph $G = (V,E)$. In mathematics a directed acyclic graph $(DAG)$ is a directed graph with no directed cycles. That is a graph such that there is no way to start at any node and follow a consistently-directed sequence of edges in E that eventually loops back to the beginning again.

A node set denoted by $V_UR \subset V$ containing several nodes is known as an unreachable node set of $G$ if, for each two different nodes $u$ and $v$ in $V_{UR}$, there is no way to start at $u$ and follow a consistently-directed sequence of edges in $E$ that finally archives the node $v$. You are asked in this problem to calculate the size of the maximum unreachable node set of a given graph $G$.

Input

The input contains several test cases and the first line contains an integer $T (1 \le T \le 500)$ which is the number of test cases.

For each case, the first line contains two integers $n (1 \le n \le 100)$ and $m (0 \le m \le n(n - 1)/2)$ indicating the number of nodes and the number of edges in the graph $G$. Each of the following $m$ lines describes a directed edge with two integers $u$ and $v (1 \le u, v \le n$ and $u \neq v)$ indicating an edge from the $u$-th node to the $v$-th node. All edges provided in this case are distinct.

We guarantee that all directed graphs given in input are DAGs and the sum of m in input is smaller than $500000$.

Output

For each test case, output an integer in a line which is the size of the maximum unreachable node set of $G$.

样例输入

3
4 4
1 2
1 3  
2 4
3 4
4 3
1 2
2 3
3 4
6 5
1 2
4 2
6 2
2 3
2 5

样例输出

2
1
3

想挑战这道题吗

  • main.c