#K90567. Ensuring Connectivity in a Road Network

    ID: 37781 Type: Default 1000ms 256MiB

Ensuring Connectivity in a Road Network

Ensuring Connectivity in a Road Network

You are given a network of n villages, where initially every village is connected to every other village (i.e. a complete graph). A postman wants to ensure that there is always a valid route between two specified villages s and t, even if k roads (edges) become impassable. However, note that in a complete graph, the network remains connected as long as the number of roads removed satisfies the condition \( k < n-1 \).

Your task is to determine for each test case whether the postman can always ensure a valid routing from village s to village t regardless of which k roads are impassable. Output Yes if the connectivity condition holds and No otherwise.

inputFormat

The input is read from standard input and has the following format:

T
n1 k1 s1 t1
n2 k2 s2 t2
... 
nT kT sT tT

Here, T is the number of test cases. For each test case, n represents the number of villages, k is the number of impassable roads, and s and t are the starting and target villages respectively.

Note: The villages are numbered arbitrarily and, for this problem, the specific values of s and t do not affect the connectivity decision.

outputFormat

For each test case, print a single line containing Yes if there is always a valid route between village s and village t regardless of which k roads become impassable; otherwise, print No.

The condition required for connectivity to be guaranteed is \( k < n-1 \).

## sample
2
4 1 1 4
3 0 1 3
Yes

Yes

</p>