有一张n个点m条边的有向无环图(点从1到n编号)和一个初始为空的集合S,每次可以在有向图中取一个同时符合下列两个条件的点x加入集合S:
1、x不在集合S中。
2、对任意已经在S中的点y,原图中都应存在一条从x到y或从y到x的路径。
当集合S为空的时候,你可以选择任何一个点添加。
你的任务就是,在上述构造s的规则下,求出S最多能够包含多少个点。
输入输出格式
输入格式:
第一行一个正整数T,表示数据组数。
每组数据第一行有两个正整数n,m,表示该图的点数与边数。
接下来m行,每行两个正整数u,v,其中u<v,表示有一条点u到点v的有向边。
输出格式:
对每组数据输出一行一个正整数表示答案。
输入输出样例
输入样例#1: 复制
2 4 4 1 2 2 4 1 3 3 4 4 4 1 3 1 4 2 3 2 4
输出样例#1:
3 2
补充说明
在第一组数据中:可以依次添加点1、点4,点3或点2;第二组数据中,可以依次添加点1、点3。 对于30%的数据,n≤15 对于60%的数据,n≤1000 对于100%的数据,1≤T≤10 ; 1≤n≤10000 ;1≤m≤30000,输入中每行两个数 u,v 都满足 u
时间限制:1s 空间限制:256M