CF243B Hydra
Description
One day Petya got a birthday present from his mom: a book called "The Legends and Myths of Graph Theory". From this book Petya learned about a hydra graph.
A non-oriented graph is a hydra, if it has a structure, shown on the figure below. Namely, there are two nodes $ u $ and $ v $ connected by an edge, they are the hydra's chest and stomach, correspondingly. The chest is connected with $ h $ nodes, which are the hydra's heads. The stomach is connected with $ t $ nodes, which are the hydra's tails. Note that the hydra is a tree, consisting of $ h+t+2 $ nodes.
Also, Petya's got a non-directed graph $ G $ , consisting of $ n $ nodes and $ m $ edges. Petya got this graph as a last year birthday present from his mom. Graph $ G $ contains no self-loops or multiple edges.
Now Petya wants to find a hydra in graph $ G $ . Or else, to make sure that the graph doesn't have a hydra.
Input Format
N/A
Output Format
N/A
Explanation/Hint
The first sample is depicted on the picture below:
