Problem E
Six Degrees

Picture by: Fo0bar

For years and years, the ICT Senior Service Desk (ISSD) of the university has been confronted with a slow wired network that gives unexpected time-outs and seemingly random slow connection speeds. A new manager has been hired to solve these problems once and for all. The manager does not have any computer science or IT knowledge, but he does happen to have a strong background in sociology. He quickly finds that the network problems only affect devices of old professors with an office in some distant corner of the building.

Obsessed by the idea of six degrees of separation, the new manager proposes a rule to counter the network problems. This rule says that any two devices in the network should be connected via at most 5 intermediary devices. So, given the current lay-out of the university’s wired computer network, he decides to prepare a list of all devices of peripheral professors that are currently not able to connect to all other devices within 6 steps. The manager’s solution to the network problems is then to disconnect all devices on this list from the wired network at once. He explicitly ignores the fact that, possibly, then disconnecting these devices in a particular order may lead to a network structure such that some devices on the list actually no longer have to be disconnected, or that afterwards additional devices may have to be disconnected or connected to reach the actual desired result.

The board of the university, not having a background in computer science, IT or sociology is also not bothered by whether or not the proposed solution is correct, but will instead only base its decision on whether or not the prepared list of devices to be disconnected is not too long, so that not too many professors would be affected. The board will therefore only approve the plan if no more than 5% of the wired network devices is on the list.

Given the lay-out of the network, in the form of a list of pairs of IP addresses or hostnames representing directly connected devices, determine whether or not the university board will allow the new manager to execute his plan.

Input

The input starts with a line containing an integer $T$ ($1 \leq T \leq 2$), the number of test cases. Then for each test case:

• One line containing an integer $1 \leq M \leq 30\, 000$ denoting the number of (directly) connected pairs of devices (with at most $3\, 000$ unique devices).

• $M$ lines, each line containing two IP addresses or hostnames of (directly) connected devices, represented by two strings of printable ASCII characters (of length $\leq 64$) without whitespace.

Each pair of connected devices is included once in the input file. All connections are bidirectional. You may assume that all devices in the university network are in the same connected component of devices.

Output

For each test case, output one line containing either YES if the plan is allowed to be executed or NO if the plan is not allowed to be executed.

2
6
132.229.123.1 132.229.123.2
132.229.123.2 132.229.123.3
132.229.123.3 132.229.123.4
132.229.123.4 132.229.123.5
132.229.123.5 132.229.123.6
132.229.123.6 xxxxx
7
a b
b c
c d
d e
e f
f g
g h

YES
NO