#316. Air Raid

Air Raid

题目描述

给定一个有向无环图,用尽量少的有向路径覆盖全部顶点。每个顶点恰好属于一条路径;单个顶点也可以作为一条路径。求最少路径条数。

输入格式

第一行测试组数。每组先输入 n、m,再输入 m 条有向边。

输出格式

每组输出最少路径条数。

样例输入

2
4
3
3 4
1 3
2 3
3
3
1 3
1 2
2 3

样例输出

2
1

题意整理;原题与输入输出格式对照。