Hi,

Can anyone tell me why this randomize solution is correct ?

Problem : 1176E - Покрывай!
Problem statement : You are given an undirected unweighted connected graph consisting of n vertices and m edges. It is guaranteed that there are no self-loops or multiple edges in the given graph. Your task is to choose at most n / 2 vertices in this graph so each unchosen vertex is adjacent (in other words, connected by an edge) to at least one of chosen vertices.
Solution : 62626593