CF653E Bear and Forgotten Tree 2

A tree is a connected undirected graph consisting of $ n $ vertices and $ n-1 $ edges. Vertices are numbered $ 1 $ through $ n $ . Limak is a little polar bear. He once had a tree with $ n $ vertices but he lost it. He still remembers something about the lost tree though. You are given $ m $ pairs of vertices $ (a_{1},b_{1}),(a_{2},b_{2}),...,(a_{m},b_{m}) $ . Limak remembers that for each $ i $ there was no edge between $ a_{i} $ and $ b_{i} $ . He also remembers that vertex $ 1 $ was incident to exactly $ k $ edges (its degree was equal to $ k $ ). Is it possible that Limak remembers everything correctly? Check whether there exists a tree satisfying the given conditions.

N/A

N/A

In the first sample, there are $ n=5 $ vertices. The degree of vertex $ 1 $ should be $ k=2 $ . All conditions are satisfied for a tree with edges $ 1-5 $ , $ 5-2 $ , $ 1-3 $ and $ 3-4 $ . In the second sample, Limak remembers that none of the following edges existed: $ 1-2 $ , $ 1-3 $ , $ 1-4 $ , $ 1-5 $ and $ 1-6 $ . Hence, vertex $ 1 $ couldn't be connected to any other vertex and it implies that there is no suitable tree.