Enter | Register
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Round 1079 (Div. 1)
C2. Interactive Graph (Hard Version) Finished
time limit per test: 2 seconds
memory limit per test: 256 megabytes → Virtual participation
This is the hard version of the problem. The difference between the versions is that in this version, you can ask no more than Virtual contest is a way to take part in past
contest, as close as possible to participation
n + m questions, and n ≤ 30. You can hack only if you solved all versions of this problem.
on time. It is supported only ICPC mode for
virtual contests. If you've seen these
This is an interactive problem. problems, a virtual contest is not for you -
solve these problems in the archive. If you
just want to solve some problem from a
The jury has thought of a directed acyclic graph without loops and multiple edges, which has n vertices and m edges. contest, a virtual contest is not for you -
solve this problem in the archive. Never use
Your task is to determine which edges are in this graph. To do this, you can ask questions of the form: what does the k -th path look like in someone else's code, read the tutorials or
communicate with other person during a
the lexicographically∗ sorted list of all paths in the graph. virtual contest.
A path in the graph is a sequence of vertices u 1 , u 2 , … , u l , such that for any i < l , there exists an edge (u i , u i+1 ) in the graph. Start virtual contest
Your task is to accomplish this by asking no more than n + m questions.
∗
A sequence a is lexicographically smaller than a sequence b if and only if one of the following holds: → Problem tags
a is a prefix of b , but a ≠ b ; or combinatorics dfs and similar dp
in the first position where a and b differ, the sequence a has a smaller element than the corresponding element in b .
graphs interactive
Input No tag edit access
Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10 ). The description of the test cases
follows.
→ Contest materials
Each test case consists of a single line with an integer n (1 ≤ n ≤ 30 ) — the number of vertices in the graph.
Announcement
The jury guarantees that the given graph does not contain cycles or multiple edges.
Note that m is unknown to you!
Interaction
The interaction for each test case begins with reading the integer n.
Then you can ask up to n + m questions.
To ask a question, output a string in the format "? k" (without quotes) (1 ≤ k ≤ 2 ). After each question, read an integer q — the
30
number of vertices in the k -th path. If q = 0, then such a path does not exist; otherwise, read q integers — the vertex numbers that make
up this path.
To report your answer, first output a string in the format "! m", and then output m lines describing the edges in the format "u v", which
means that there is an edge leading from u to v. You can output the edges in any order. Outputting the answer does not count as a query.
30
It can be shown that under the given constraints, the number of distinct paths in the graph does not exceed 2 .
After printing each query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit
∗
exceeded verdict.
If, at any interaction step, you read −1 instead of valid data, your solution must exit immediately. This means that your solution will receive
Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution
will continue to read from a closed stream.
Hacks:
For hacks, use the following format:
The first line should contain a single integer t (1 ≤ t ≤ 10 ) — the number of test cases.
n⋅(n−1)
The first line of each case should contain two integers n, m (1 ≤ n ≤ 30 ,0 ≤ m ≤
2
) — the number of vertices and edges in the
graph.
The next m lines should contain descriptions of the edges. Each edge is defined by two integers v, u (1 ,
≤ v, u ≤ n v ≠ u ), meaning an
edge from vertex v to vertex u .
The graph cannot contain cycles or multiple edges.
∗
To flush, use:
fflush(stdout) or [Link]() in C++;
[Link]() in Python;
see the documentation for other languages.
Example
input Copy
3
5
1 1
2 1 2
3 1 2 4
3 1 2 5
2 1 3
3 1 3 4
3 1 3 5
1 2
1 3
1 4
1 5
1 1
1 2
2 2 1
output Copy
? 1
? 2
? 3
? 4
? 5
? 6
? 7
? 8
? 11
? 14
? 15
! 6
1 3
1 2
2 4
3 4
2 5
3 5
? 2
! 0
? 1
? 2
? 3
! 1
2 1
Note
The graph for the first test case.
In this graph, there are 15 paths, which are arranged in lexicographic order as follows:
1 → 2
1 → 2 → 4
1 → 2 → 5
1 → 3
1 → 3 → 4
1 → 3 → 5
2 → 4
2 → 5
3 → 4
3 → 5
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Feb/12/2026 17:28:22UTC+5.5 (g1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by