6단계 분리

대학의 ICT 지원 데스크(ISSD)는 몇 해째 느린 유선 네트워크에 시달렸다. 접속은 예고 없이 끊기고 속도도 들쭉날쭉하다. 대학은 이 문제를 끝내려고 새 관리자를 뽑았다. 그는 전산이나 IT 지식은 없지만 사회학 소양이 두텁다. 그는 장애가 건물 구석진 자리에 연구실을 둔 노교수의 장비에서만 일어난다는 사실을 금방 알아냈다.

여섯 다리만 건너면 누구와도 이어진다는 생각에 빠진 관리자는 규칙 하나를 내놓는다. 네트워크의 어떤 두 장비든 중간 장비를 5대 이하만 거쳐서 이어져야 한다. 다시 말해 두 장비를 잇는 최단 경로가 연결선 6개 이하로 이루어져야 한다. 관리자는 지금 배선을 보고 다른 모든 장비에 6단계 안으로 닿지 못하는 장비를 전부 적어 명단을 만들고, 명단에 오른 장비를 한꺼번에 네트워크에서 떼어내려 한다. 명단의 장비를 어떤 순서로 떼면 그중 일부는 떼지 않아도 되고, 반대로 나중에 다른 장비를 더 떼거나 이어야 할 수도 있다는 점을 그는 대놓고 무시한다.

대학 이사회는 전산도 IT도 사회학도 모르므로 이 방안이 옳은지는 따지지 않는다. 이사회는 명단이 너무 길지 않은지만 본다. 유선 네트워크 장비 전체의 5% 이하만 명단에 올라 있을 때 이사회는 계획을 승인한다.

직접 이어진 장비 쌍의 목록으로 배선이 주어진다. 이사회가 관리자의 계획을 승인할지 판정하라.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10$)가 주어진다. 각 테스트 케이스는 다음 형식이다.

• 첫 줄에 직접 이어진 장비 쌍의 개수 $M$ ($1 \le M \le 30000$)이 주어진다. 한 테스트 케이스에 나오는 서로 다른 장비는 3000대 이하다.
• 이어지는 $M$개 줄에 직접 이어진 두 장비의 IP 주소 또는 호스트명이 주어진다. 각 이름은 공백이 없는 길이 64 이하의 ASCII 문자열이다.

이어진 장비 쌍은 각각 입력에 한 번만 나오고, 모든 연결은 양방향이다. 한 테스트 케이스의 모든 장비는 하나의 연결 요소에 속한다. 모든 테스트 케이스의 $M$을 더한 값은 30000을 넘지 않는다.

각 테스트 케이스마다 한 줄에, 계획을 실행해도 되면 YES를, 안 되면 NO를 출력한다.