Задача Small Country

Описание

Constructor LEGO was presented to Asan. He was so overjoyed and immediately started to collect a small country. He decided to represent bricks as small cities and started to pave ways between them in order specified in the instruction.

Now Asan wants to know the road's id number in the instruction after adding which all of bricks will be connected.

Формат входных данных

You are given N (2 <= N <= 1000) - number of bricks and M (1 <= M <= 10 ⁶ ) - number of instructions. Each of the following M lines contain two numbers each - id numbers of bricks which must be connected by the road.

Формат выходных данных

Output one number - id number of the road in the instruction after adding which all of brick will be connected, and -1 if it is impossible to connect all of bricks.