전설

캐나디아라는 나라는 도시와 도로로 이루어져 있다. 모든 도로는 양방향으로 다닐 수 있고, 도로를 따라 어떤 도시에서든 다른 모든 도시로 갈 수 있다.

수지는 캐나디아 사람들의 창조 신화를 연구한다. 수지가 특히 관심을 두는 신화는 다섯 개이고, 각각이 이 문제의 다섯 서브태스크에 대응한다. 다섯 신화는 서로 매우 비슷하며 모두 다음과 같은 형태이다.

태초에 캐나디아의 도로망은 특정한 구조였다. 시간이 흐르면서 늘어나는 인구의 필요에 맞춰 도로망이 바뀌었다. 각 변경은 다음 중 하나였다.

• 아직 서로 직접 잇는 도로가 없는 두 도시 사이에 도로를 하나 건설했다.
• 새 도시를 하나 건설했다. 이렇게 세운 도시는 처음에는 기존 도시 어느 것과도 연결되어 있지 않다.
• 도시 $u$가 너무 커져서 두 도시 $v$와 $w$로 나뉘었다. 원래 $u$와 도로로 직접 이어져 있던 도시들을 두 집합 $A$와 $B$로 나눈 뒤, $A$의 각 도시와 $v$ 사이, $B$의 각 도시와 $w$ 사이, 그리고 $v$와 $w$ 사이에 도로를 건설한다.

예를 들어 에서 가운데 도시가 나뉘면 도로망은 가 된다.

다섯 신화는 캐나디아가 처음에 어떤 구조였다고 믿는지만 다르다. 각 신화가 말하는 처음 구조는 다음과 같다.

서브태스크와 신화	그림	처음 구조
1. 플라스크 신화		도시 4개 $a, b, c, d$와 도로 5개 $a$-$b$, $a$-$c$, $b$-$c$, $a$-$d$, $b$-$d$ ($c$와 $d$를 제외한 모든 두 도시가 이어져 있다)
2. 달 신화		도시 3개를 도로 3개로 이은 사이클 (삼각형)
3. 태양 신화		도시 4개를 도로 4개로 이은 사이클
4. 독수리 발톱 신화		도시 하나가 다른 도시 3개와 각각 이어져 있다 (도시 4개, 도로 3개)
5. 여우 신화		도시 5개 $a, b, c, d, e$와 도로 5개 $a$-$b$, $b$-$c$, $c$-$a$, $a$-$d$, $b$-$e$ (삼각형의 두 꼭짓점에 도시가 하나씩 더 달려 있다)

각 서브태스크마다 캐나디아의 현재 도로망이 주어진다. 위의 변경을 적절한 순서로 0번 이상 적용해서 신화가 말하는 처음 구조를 도시 번호를 무시하고 주어진 도로망과 똑같이 만들 수 있으면 그 신화는 옳을 수도 있다. 신화가 옳을 수도 있는지 판별하라.

첫째 줄에 풀어야 할 서브태스크 번호 $S$ ($1 \le S \le 5$)가 주어진다. 둘째 줄에 테스트 케이스의 수 $T$ ($1 \le T$)가 주어진다.

각 테스트 케이스는 빈 줄 하나로 시작하고, 그다음 줄에 도시의 수 $N$과 도로의 수 $M$ ($2 \le N$, $1 \le M$)이 주어진다. 도시는 $1$번부터 $N$번까지 번호가 붙어 있다. 이어서 $M$개의 줄에 두 정수 $a$와 $b$ ($1 \le a, b \le N$)가 주어지며, 도시 $a$와 도시 $b$가 도로로 이어져 있다는 뜻이다. 도시를 자기 자신과 잇는 도로는 없고, 같은 두 도시를 잇는 도로가 둘 이상 있는 경우도 없다. 도로를 따라 어떤 도시에서든 다른 모든 도시로 갈 수 있다.

서브태스크 3에서는 모든 테스트 케이스의 $N$의 합이 $10^5$ 이하이고 $M$의 합도 $10^5$ 이하이다. 나머지 서브태스크에서는 모든 테스트 케이스의 $N$의 합이 $1000$ 이하이고 $M$의 합도 $1000$ 이하이다.

각 테스트 케이스마다 신화가 옳을 수도 있으면 YES, 아니면 NO를 한 줄에 출력한다.