CF1007D Ants

There is a tree with $ n $ vertices. There are also $ m $ ants living on it. Each ant has its own color. The $ i $ -th ant has two favorite pairs of vertices: ( $ a_i, b_i $ ) and ( $ c_i, d_i $ ). You need to tell if it is possible to paint the edges of the tree in $ m $ colors so that every ant will be able to walk between vertices from one of its favorite pairs using only edges of his color; if it is possible, you need to print which pair every ant should use.

N/A

N/A

In the sample, the second and the third edge should be painted in the first color, the first and the fifth should be painted in the second color, and the fourth should be painted in the third color.