zzq的离散数学教室2
题号:NC15560
时间限制:C/C++/Rust/Pascal 3秒,其他语言6秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

  离散数学中有种名叫“偏序集”的东西。

    在这个题目中,集合中有n个元素,编号从1到n。它们之间共有m对偏序关系(1<=m<=2n),每一对偏序关系的表示形式为以空格分开的两个编号:x y。含义是x和y之间有关系≤。(这里的≤不是传统意义上的小于等于,可以理解为从y到x的一条有向边),记做:x≤y。同时这些关系也具有传递性,例如,如果x≤y并且y≤z,那么可以得到x≤z。数据保证不会出现同时有x≤y,y≤z,z≤x的情况。

    现在我们的问题是,要你从n个元素里尽可能多的选出一些元素,使得这些元素之间不满足偏序关系。(即这些点中,任意两点都不存在偏序关系).问你最多能选几个元素。 

输入描述:

第一行一个数T,代表有T组数据
下一行,包含2个正整数n和m,中间由空格分开。(2<=n<=100,000,n的总和 <= 300,000)
接下来m行,为m个偏序关系,每行2个整数x和y,即表示编号为x的元素和编号为y的元素有关系:x≤y

输出描述:

每组数据输出一行,每行一个整数,最多能选的元素数量。
示例1

输入

复制
1
5 5
1 2
2 3
2 4
2 5
4 5

输出

复制
2

备注:

偏序集在百度百科上的定义是这样的:
设R为非空集合A上的关系,如果R是自反的、反对称的和可传递的,则称R为A上的偏序关系,简称偏序,通常记作≦。一个集合A与A上的偏序关系R一起叫作偏序集,记作或。其中(自反性)对任一,则x≦x;(反对称性)如果x≦y,且y≦x,则x=y;(传递性)如果x≦y,且y≦c ,则x≦c。