Six Degrees

For years the university ICT Senior Service Desk (ISSD) has dealt with a slow wired network that drops connections without warning and delivers uneven speeds. The university hired a new manager to end the problem. He knows no computer science and no IT, but his background in sociology is strong. He soon notices that the failures only hit devices belonging to old professors whose offices sit in far corners of the building.

Taken with the idea of six degrees of separation, the manager proposes one rule. Any two devices in the network must be connected through at most 5 intermediary devices. In other words, the shortest path between two devices must use at most 6 links. Looking at the current wiring, he writes down every device that cannot reach all other devices within 6 steps, and he plans to disconnect every device on that list at once. He openly ignores that disconnecting the listed devices in some order could leave part of the list unnecessary, or force further devices to be disconnected or connected afterwards.

The university board knows nothing about computer science, IT or sociology, so it does not ask whether the plan is correct. The board only checks that the list is not too long, so that few professors are affected. The board approves the plan when at most 5% of the wired network devices are on the list.

The wiring is given as a list of pairs of directly connected devices. Decide whether the board lets the manager carry out his plan.

The first line contains the number of test cases $T$ ($1 \le T \le 10$). Each test case has the following format.

• One line with the number of directly connected device pairs $M$ ($1 \le M \le 30000$). A single test case contains at most 3000 distinct devices.
• $M$ lines, each with the IP addresses or hostnames of two directly connected devices. Each name is an ASCII string of length at most 64 with no whitespace.

Each connected pair appears exactly once in the input, and every connection is bidirectional. All devices of one test case belong to a single connected component. The sum of $M$ over all test cases is at most 30000.

For each test case, print one line containing YES if the plan may be carried out, and NO otherwise.