#K90567. Ensuring Connectivity in a Road Network
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 \).
## sample2
4 1 1 4
3 0 1 3
Yes
Yes
</p>