P30106

仙人掌

难度 7 级 强连通分量 图论
讨论 统计 1通过 1提交 100%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

  1. 这是一个强连通图。
  2. 图中的每条边属于一个环,并且只属于一个环。

我们称这个图为 CACTUS(仙人掌图)。

上面的图是一个例子。左边的是一个仙人掌图,而右边的不是。因为右图中的边 (0, 1) 属于两个环,分别是 (0, 1, 3) 和 (0, 1, 2, 3)。

输入

输入由多个测试用例组成。第一行包含一个整数 T(1 \le T \le 10),表示测试用例的数量。

对于每个测试用例,第一行包含一个整数 n(1 \le n \le 20000),表示点的数量。

接下来的每一行有两个数字 a 和 b,表示一条单向边 (a \to b)。每个测试用例以 (0, 0) 结束。

注意:边的总数不超过 50000。

输出

对于每个测试用例,输出一行包含 YES 或 NO,表示该图是否为仙人掌图。

样例

样例 1
输入
2
4
0 1
1 2
2 0
2 3
3 2
0 0
4
0 1
1 2
2 3
3 0
1 3
0 0
输出
YES
NO

提示

  • 1 \le n \le 20000
  • 边总数 \le 50000
  • 1 \le T \le 10
Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交