그랜드 테스트

제레미, 리처드, 제임스는 자동차를 시험하기를 좋아한다. 시험할 장소를 정하는 일은 늘 어렵다. 세 사람은 나라를 하나 고른 뒤 그 나라의 도시와, 도시를 잇는 양방향 도로를 살핀다.

시험을 하려면 서로 다른 두 도시 $S$와 $F$, 그리고 $S$에서 $F$로 가는 경로 세 개가 필요하다. 경로는 도시의 수열 $v_1, v_2, \dots, v_k$이며 $v_1 = S$, $v_k = F$이고, $1 \le i \le k-1$인 모든 $i$에 대해 $v_i$와 $v_{i+1}$을 잇는 도로가 있다. 한 경로 안에 같은 도시가 두 번 나오지는 않는다.

경로 세 개는 두 조건을 지켜야 한다. $S$와 $F$를 뺀 모든 도시는 세 경로 가운데 많아야 한 경로에만 나온다. 어떤 도로도 두 경로 이상에 쓰이지 않는다.

조건을 만족하는 $S$, $F$와 경로 세 개가 있으면 세 사람은 각자 $S$에서 차를 몰고 서로 다른 경로로 달려 누가 $F$에 먼저 닿는지 겨룬다.

나라 여러 개의 정보가 주어진다. 각 나라마다 위 조건대로 두 도시와 경로 세 개를 고를 수 있는지 판정한다.

첫 줄에 나라의 수 $T$가 주어진다 ($1 \le T \le 100\,000$). 이어서 나라 $T$개의 정보가 주어진다.

각 나라의 첫 줄에는 도시의 수 $n$과 도로의 수 $m$이 주어진다 ($1 \le n, m \le 100\,000$). 다음 $m$개 줄에는 도로의 양 끝 도시 $u_i$와 $v_i$가 주어진다 ($1 \le u_i < v_i \le n$). 모든 도로는 양방향이고, 두 도시를 잇는 도로는 많아야 한 개다.

모든 나라의 $n$을 더한 값과 $m$을 더한 값은 각각 $100\,000$ 이하다.

각 나라마다 한 줄에 답을 출력한다. 조건을 만족하는 두 도시 $S$, $F$와 경로 세 개가 있으면 YES를, 없으면 NO를 출력한다. 답은 입력에 주어진 나라 순서대로 출력한다.