27205번 - Wires Puzzle 다국어인터랙티브

문제

This is interactive problem. Your program will interact with judges' program using standard input and standard output.

Friends are planing a puzzle which has the following structure. There are $n$ similar wires put through the opaque pipe. One of the pipe ends is the left one, another is the right one. The friends see $n$ wires at each end of the pipe, the wires are labeled by distinct integers from 1ドル$ to $n$ at each end, but a wire can have different labels at different ends of the pipe.

The goal of the puzzle is to make correspondence between wire ends, that is --- for each $i$ from 1ドル$ to $n$ find the number $a_i$ such that the wire with $i$ on the right end is marked with $a_i$ on the left end.

To solve the puzzle it is possible to make the following requests. You can choose an integer $k$ (1ドル \le k \le n$) and divide the wires at the right end to $k$ non-empty groups, connecting all wires inside the same group. After that using a special device it is possible to detect for each pair of wires at their left end, whether their right ends are connected. Therefore for the left ends of the wires it is now known which labels correspond to the wires from the same group.

It is required to find the correspondence between left and right ends of the wires, using exactly three such queries.

To better understand the actions in the problem, it is recommended to study the example description below.

입력

출력

제한

인터랙션 프로토콜

First your program must read the integer $n$ from standard input (3ドル \le n \le 200$). Then it must make exactly three queries.

To make a query first print a single integer $k$ on a line by itself --- the number of groups. It must be followed by $n$ integers $g_1, g_2, \ldots, g_n$. Each integer must be from 1ドル$ to $k,ドル each integer from 1ドル$ to $k$ must occur at least once. The number $g_i$ gives the number of the group that the right end of the wire labeled with $i$ goes to. All right ends that are in the same group get connected.

The judges' program responds with the information which labels on the left ends of the wires correspond to the same group of wires. The format is the following: the information about $k$ groups will be printed. The information about the $j$-th group starts with an integer $s_j$ on a line by itself --- the size of the group. It is followed by $s_j$ integers --- the labels on the left ends of the wires that are in this group. The order of groups and the order of wires inside the groups can be arbitrary, at the judges' program's discretion. Specially, it can be different from the numbering of groups in the query.

After performing exactly three queries, your program must print $n$ integers $a_1, a_2, \ldots, a_n,ドル where $a_i$ is the label of the left end of the wire with the label $i$ at its right end.

힌트

Consider the example above.

There are 4 wires.

The first query: there are three groups, the wires with right labels 1 and 2 are connected, the wire with right label 3 is in a group by itself, so is the wire with right label 4.

The judges' program responds that the wires with left labels 2 and 3 are in the same group, the wire with the left label 1 is in a group by itself, and so is the wire with the left label 4.

Analyzing the response, the contestant's program understands that the wires with left labels 2 and 3 are in some order the wires with right labels 1 and 4, and the wires with left labels 1 and 4 are in some order the wires with right labels 3 and 4.

The second query has two groups of wires, wires with right labels 1, 2 and 3 are connected, the wire with right label 4 is in a group by itself.

The judges' program responds that the wires with left labels 2, 3 and 4 have the right ends connected.

The contestant's program understands that the wire with the right label 4 is has its left label 1, therefore the wire with the right label 3 has its left label 4.

The third query similarly allows to distinguish between wires with right labels 1 and 2. Now the correspondence is clear.