CF2196C2 Interactive Graph (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, you can ask no more than $ n + m $ questions, and $ n \leq 30 $ . You can hack only if you solved all versions of this problem. This is an interactive problem. The jury has thought of a directed acyclic graph without loops and multiple edges, which has $ n $ vertices and $ m $ edges. 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 the lexicographically $ ^{\text{∗}} $ sorted list of all paths in the graph. A path in the graph is a sequence of vertices $ u_{1}, u_{2}, \dots, u_{l} $ , such that for any $ i \lt l $ , there exists an edge ( $ u_{i}, u_{i + 1} $ ) in the graph. Your task is to accomplish this by asking no more than $ n + m $ questions. $ ^{\text{∗}} $ A sequence $ a $ is lexicographically smaller than a sequence $ b $ if and only if one of the following holds: - $ a $ is a prefix of $ b $ , but $ a \ne b $ ; or - in the first position where $ a $ and $ b $ differ, the sequence $ a $ has a smaller element than the corresponding element in $ b $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10 $ ). The description of the test cases follows. Each test case consists of a single line with an integer $ n $ ( $ 1 \le n \le 30 $ ) — the number of vertices in the graph. The jury guarantees that the given graph does not contain cycles or multiple edges. Note that $ m $ is unknown to you!

N/A

The graph for the first test case. In this graph, there are $ 15 $ paths, which are arranged in lexicographic order as follows: - $ 1 $ - $ 1 \to 2 $ - $ 1 \to 2 \to 4 $ - $ 1 \to 2 \to 5 $ - $ 1 \to 3 $ - $ 1 \to 3 \to 4 $ - $ 1 \to 3 \to 5 $ - $ 2 $ - $ 2 \to 4 $ - $ 2 \to 5 $ - $ 3 $ - $ 3 \to 4 $ - $ 3 \to 5 $ - $ 4 $ - $ 5 $