Bajtocy has just been appointed Chief Architect of Bajtocja. Bajtocja consists of $n$ ($1 \le n \le 200\,000$) cities connected by $m$ ($1 \le m \le 300\,000$) bidirectional roads, each with a maintenance cost that is a positive integer. Cities and roads are numbered from $0$ to $n-1$ and from $0$ to $m-1$, respectively. It is known that the road network allows travel between any two cities, and the maintenance costs of the roads are pairwise distinct. Each pair of cities is connected by at most one road. No road connects a city to itself.

With his rather unexpected promotion, Bajtocy has been given a difficult task: King Bajtazar would like to close some roads such that it is still possible to travel between any two cities. Naturally, he wants to minimize the sum of the maintenance costs of the remaining roads. Bajtocy has been asked to determine which roads should be kept.

Unfortunately, Bajtocy does not know the maintenance costs of the individual roads. However, he can ask his advisors questions. Each question is of one of two types. An independent type question is a comparison of the costs of two roads that do not share any endpoints. A star type question is to determine, among a given set of roads that share a common endpoint, which one has the minimum cost. Help Bajtocy determine which roads to keep, using only these two types of queries.

Interaction

This is an interactive problem. Communication with the grader can take place either using a library or via standard input and output. You must not use both methods simultaneously.

Your program must not open any files. The program may use standard diagnostic output (stderr), but remember that this consumes time. Any redundant data printed to standard output may be treated as an incorrect answer.

Option 1: Communication via library

In this option, your program must not use standard input and output.

C++ At the beginning of the program, you must include: #include "redlib.h"

The library provides the following functions: int DajN() – Returns the number $n$ of cities in Bajtocja. std::vector<std::pair<int,int> > DajDrogi() – Returns $m$ pairs of integers $(x, y)$ ($0 \le x, y < n, x \neq y$) representing the roads. Roads are numbered in the order returned by this function. int Niezalezne(int a, int b) – Compares roads $a$ and $b$ ($0 \le a, b < m$) that do not share a common endpoint; returns $-1$ if road $a$ is cheaper, and $1$ if road $b$ is cheaper. int Gwiazda(std::vector<int> t) – Compares a set of roads with a common endpoint; the vector $t$ contains the road numbers, and the result is the number of the cheapest road in this set. * void Wynik(std::vector<int> t) – Submits the set of road numbers to be kept. After executing this function, the program must terminate.

Python At the beginning of the program, you must include: from redlib import DajN, DajDrogi, Niezalezne, Gwiazda, Wynik

The library provides the following functions: DajN() -> int DajDrogi() -> list[tuple[int, int]] Niezalezne(a : int, b : int) -> int Gwiazda(t : list[int]) -> int * Wynik(t : list[int])

Option 2: Communication via standard input/output

The first line of standard input contains two integers $n$ and $m$. The next $m$ lines each contain two integers $x$ and $y$ ($0 \le x, y < n, x \neq y$) representing the roads. Roads are numbered $0$ to $m-1$ in the order they appear in the input.

To ask an independent type question, print: 1 a b. The grader returns $-1$ if road $a$ is cheaper, and $1$ if road $b$ is cheaper.

To ask a star type question, print: 2 k r_1 r_2 ... r_k, where $k$ is the number of roads and $r_i$ are the road indices. The grader returns the index of the cheapest road.

To submit the answer, print: 3 k r_1 r_2 ... r_k.

For C++, use std::endl or fflush(stdout) after every output. For Python, use flush=True.

Subtasks

The score for a test is determined by the number of independent queries ($p$) and star queries ($q$):

Examples

Input 1

4 4
0 3
0 2
1 2
2 3

Output 1

2 3 3 1 2
1 0 2
2 2 3 0
1 2 0
3 3 0 2 1

Note

In this example, $n=4, m=4$. The roads are $(0,3), (0,2), (1,2), (2,3)$ with costs $3, 1, 2, 4$. The queries determine the relative costs to find the Minimum Spanning Tree.