문제
방향성그래프는 정점들(V)과 방향을 표현하는 간선들(E)로 이루어져 있다.
간선(u,v)는 u에서 v로의 방향을 나타낸다. ((v,u)는 반대방향을 의미한다.)
방향성그래프에서 유방향 순환은 아래와 같이 간선들의 순서들로 나타낸다.
(u1, v1),(u2, v2),...,(uk, vk)
여기서 u의 i+1번째와 v의 i번째는 같고, i=1~(k-1)까지 반복된다.
u의 i번째와 u의 j번째가 같지 않으면, 반드시 i와 j도 같지 않다.
이런 조건에서의 유방향 순환은 간단하다.
강연결 유방향 그래프(strongly connected directed graph)에서는,
몇 개의 유방향 그래프의 모든 정점들은 u와 v의 모든 쌍으로 되어 있고, u와 v모두를 방문하게 된다.
유방향 그래프가 강연결이고 각 간선이 어떤 단순 유방향 순환에 정확히 한 번씩 포함 되는 경우에만 opunita(선인장)이 된다.
첫 번째 그래프는 opunita지만, 두 번째의 경우 간선 (0,1) 와 같은 경우 때문에 opunita가 되지 않는다.
선인장 이름의 유래는 나무와 같은 식으로,
여러 개의 단순 순환들이 연결되어 구조를 이루는데, 이것이 흡사 선인장과 같아서 선인장이란 이름이 붙었다.
주어진 유방향 그래프가 opunita가 되는지를 판단해라. 그래프는 수천개의 정점들을 가질 수 있다.
입력
첫 번째 줄에는 테스트 케이스의 개수 T (T≤20)이 입력된다.
두 번째 줄에는 10,000이 이하의 정점들의 개수가 입력되며, 세 번째 줄에는 10,000 이하의 간선의 개수가 입력된다.
그 다음의 나머지 줄에는 간선의 정보를 위해 2개의 숫자 u와 v가 입력되는데, 이는 정점 u에서 정점 v로 향하는 간선이 존재한다는 것이다.
u = v 가 동일한 경우는 없다.
출력
opunita면 "YES" 아니면 "NO" 츌력 하시오.
예제1
2
4
5
01
12
20
23
32
4
5
01
12
23
30
13
YES
NO