#z1052. 路径

路径

【问题描述】

给定一张 n 个点,m 条边的有向图,你需要判断是否存在两个点 u,v,使得不存在从 u 到 v 的路径,也不存在从 v 到 u 的路径。

【输入格式】

第一行一个数 T表示数据组数,之后 T组数据。 对于每组数据: 第一行两个正整数 n,m,表示有向图的点数和边数,之后 m 行每行 2 个正整数 xi,yi,表示一条从 xi 到 yi 的有向边。

【输出格式】

对于每组数据,若存在这样的点对则输出 yes,否则输出 no。

【输入样例】 2 3 3 1 2 2 3 3 1 3 2 1 2 1 3 【输出样例】 no yes 【样例解释】

对于第二组样例,2 号点和 3 号点之间互相都不存在路径抵达对方。

【数据规模和约定】

  • 对于 30% 的数据,保证 n≤100,m≤300。
  • 对于 70% 的数据,保证 n≤1000,m≤5000。
  • 对于 100% 的数据,保证 n≤5×104,m≤105,T≤10。