Prepare lawyers

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk lives in a country with a very interesting history. This country has existed for \(h\) years. In the first year of its existence, only one city was built — the capital. Each subsequent year, for each city built in the previous year, two additional cities were built, which were connected to it by bidirectional roads. Thus, after \(h\) years, the country had exactly \(2^h-1\) cities and \(2^h-2\) roads.

Recently, some imp "to improve the country’s infrastructure" built exactly three additional roads between certain pairs of cities. By doing this, in Zenyk’s opinion, all the beauty of the country was lost, and he decided to file a lawsuit against this person.

Zenyk has a list of all the roads in the country, but he does not know when each road was added, nor how the cities are numbered. In order to prepare the lawsuit, he needs to know which three of these roads could have been added last. Help him find them.

Input

The first line contains a single integer \(h\) — the number of years Zenyk’s homeland has existed.

The next \(2^h+1\) lines contain pairs of integers, one pair per line. Each of these pairs denotes the numbers of the cities connected by the corresponding road.

Cities are numbered with integers from 1 to \(2^h-1\) inclusive.

Roads are numbered with integers from 1 to \(2^h+1\) inclusive, in the order of the input data.

Output

In a single line, output three distinct integers separated by a space — the numbers of the roads that could have been added last.

If there are multiple possible answers, first minimize the first number, then minimize the second, and then — the third.

If no answer exists, i.e., the list of roads is invalid, output -1.

Constraints

\(2 \le h \le 10\).

Samples