Upd: 之后发现这个猫娘是出题组的二次元形象

## A - Two Permutations

You are given three integers $$n$$, $$a$$, and $$b$$. Determine if there exist two permutations $$p$$ and $$q$$ of length $$n$$, for which the following conditions hold:

• The length of the longest common prefix of $$p$$ and $$q$$ is $$a$$
• The length of the longest common suffix of $$p$$ and $$q$$ is $$b$$

A permutation of length $$n$$ is an array containing each integer from $$1$$ to $$n$$ exactly once. For example, $$[2,3,1,5,4]$$ is a permutation, but $$[1,2,2]$$ is not a permutation ($$2$$ appears twice in the array), and $$[1,3,4]$$ is also not a permutation ($$n=3$$ but there is $$4$$ in the array)

### Input

Each test contains multiple test cases. The first line contains a single integer $$t$$ ($$1\leq t\leq 10^4$$) — the number of test cases. The description of test cases follows

The only line of each test case contains three integers $$n$$, $$a$$, and $$b$$ ($$1\leq a,b\leq n\leq 100$$)

### Output

For each test case, if such a pair of permutations exists, output "Yes"; otherwise, output "No". You can output each letter in any case (upper or lower)

### Note

In the first test case, $$[1]$$ and $$[1]$$ form a valid pair

In the second test case and the third case, we can show that such a pair of permutations doesn't exist

In the fourth test case, $$[1,2,3,4]$$ and $$[1,3,2,4]$$ form a valid pair

Show code

## B - Elimination of a Ring

Define a cyclic sequence of size $$n$$ as an array $$s$$ of length $$n$$, in which $$s_n$$ is adjacent to $$s_1$$

Muxii has a ring represented by a cyclic sequence $$a$$ of size $$n$$

However, the ring itself hates equal adjacent elements. So if two adjacent elements in the sequence are equal at any time, one of them will be erased immediately. The sequence doesn't contain equal adjacent elements initially

Muxii can perform the following operation until the sequence becomes empty:

• Choose an element in $$a$$ and erase it

For example, if ring is $$[1, 2, 4, 2, 3, 2]$$, and Muxii erases element $$4$$, then ring would erase one of the elements equal to $$2$$, and the ring will become $$[1, 2, 3, 2]$$

Muxii wants to find the maximum number of operations he could perform

Note that in a ring of size $$1$$, its only element isn't considered adjacent to itself (so it's not immediately erased)

### Input

Each test contains multiple test cases. The first line contains a single integer $$t$$ ($$1\leq t\leq 100$$) — the number of test cases. The description of test cases follows

The first line of each test case contains a single integer $$n$$ ($$1\leq n\leq 100$$) — the size of the cyclic sequence

The second line of each test case contains $$n$$ integers $$a_1,a_2,\ldots,a_n$$ ($$1\leq a_i\leq n$$) — the sequence itself

It's guaranteed that $$a_i\ne a_{i+1}$$ for $$1\leq i<n$$

It's guaranteed that $$a_n\ne a_1$$ when $$n>1$$

### Output

For each test case, output a single integer — the maximum number of operations Muxii can perform

### Note

In the first test case, you can erase the second element first, then erase the remaining elements one by one in any order. In total, you can perform the operation $$4$$ times. Note that if you erase the first element first, then the sequence will be turned into $$[2,3,2]$$ and then immediately become $$[2,3]$$

In the second test case, you can erase the first element first, then the sequence becomes $$[2,1]$$. Then you can erase all remaining elements one by one in any order

Show code

## C - Set Construction

You are given a binary matrix $$b$$ (all elements of the matrix are $$0$$ or $$1$$) of $$n$$ rows and $$n$$ columns

You need to construct a $$n$$ sets $$A_1, A_2, \ldots, A_n$$, for which the following conditions are satisfied:

• Each set is nonempty and consists of distinct integers between $$1$$ and $$n$$ inclusive
• All sets are distinct
• For all pairs $$(i,j)$$ satisfying $$1\leq i, j\leq n$$, $$b_{i,j}=1$$ if and only if $$A_i\subsetneq A_j$$. In other words, $$b_{i, j}$$ is $$1$$ if $$A_i$$ is a proper subset of $$A_j$$ and $$0$$ otherwise

Set $$X$$ is a proper subset of set $$Y$$, if $$X$$ is a nonempty subset of $$Y$$, and $$X \neq Y$$

It's guaranteed that for all test cases in this problem, such $$n$$ sets exist. Note that it doesn't mean that such $$n$$ sets exist for all possible inputs

If there are multiple solutions, you can output any of them

### Input

Each test contains multiple test cases. The first line contains a single integer $$t$$ ($$1\le t\le 1000$$) — the number of test cases. The description of test cases follows

The first line contains a single integer $$n$$ ($$1\le n\le 100$$)

The following $$n$$ lines contain a binary matrix $$b$$, the $$j$$-th character of $$i$$-th line denotes $$b_{i,j}$$

It is guaranteed that the sum of $$n$$ over all test cases does not exceed $$1000$$

It's guaranteed that for all test cases in this problem, such $$n$$ sets exist

### Output

For each test case, output $$n$$ lines

For the $$i$$-th line, first output $$s_i$$ $$(1 \le s_i \le n)$$ — the size of the set $$A_i$$. Then, output $$s_i$$ distinct integers from $$1$$ to $$n$$ — the elements of the set $$A_i$$

If there are multiple solutions, you can output any of them

It's guaranteed that for all test cases in this problem, such $$n$$ sets exist

### Note

In the first test case, we have $$A_1 = \{1, 2, 3\}, A_2 = \{1, 3\}, A_3 = \{2, 4\}, A_4 = \{1, 2, 3, 4\}$$. Sets $$A_1, A_2, A_3$$ are proper subsets of $$A_4$$, and also set $$A_2$$ is a proper subset of $$A_1$$. No other set is a proper subset of any other set

In the second test case, we have $$A_1 = \{1\}, A_2 = \{1, 2\}, A_3 = \{1, 2, 3\}$$. $$A_1$$ is a proper subset of $$A_2$$ and $$A_3$$, and $$A_2$$ is a proper subset of $$A_3$$

Show code

## D - Carry Bit

Let $$f(x,y)$$ be the number of carries of $$x+y$$ in binary (i. e. $$f(x,y)=g(x)+g(y)-g(x+y)$$, where $$g(x)$$ is the number of ones in the binary representation of $$x$$)

Given two integers $$n$$ and $$k$$, find the number of ordered pairs $$(a,b)$$ such that $$0 \leq a,b < 2^n$$, and $$f(a,b)$$ equals $$k$$. Note that for $$a\ne b$$, $$(a,b)$$ and $$(b,a)$$ are considered as two different pairs

As this number may be large, output it modulo $$10^9+7$$

### Input

The only line of each test contains two integers $$n$$ and $$k$$ ($$0\leq k<n\leq 10^6$$)

### Output

Output a single integer — the answer modulo $$10^9+7$$

### Note

Here are some examples for understanding carries:

\begin{aligned} & \begin{array}{r} 1{\ \ }1{\ \ }1\\ +\ _{1}1_{\ \ }0{\ \ }0\\ \hline \ 1{\ \ }0{\ \ }1{\ \ }1 \end{array} & \begin{array}{r} \ 1{\ \ }0{\ \ }1\\ +\ _{\ \ }0_{\ \ }0{}_{1}1\\ \hline \ 0{\ \ }1{\ \ }1{\ \ }0 \end{array} & &\begin{array}{r} \ 1{\ \ }0{\ \ }1\\ +\ _{1}0_{1}1{}_{1}1\\ \hline \ 1{\ \ }0{\ \ }0{\ \ }0 \end{array} \end{aligned}

So $$f(7,4)=1$$, $$f(5,1)=1$$ and $$f(5,3)=3$$

In the first test case, all the pairs meeting the constraints are

$\begin{array}{lllll} (1,1)&(1,5)&(2,2)&(2,3)&(3,2)\\ (4,4)&(4,5)&(4,6)&(4,7)&(5,1)\\ (5,4)&(5,6)&(6,4)&(6,5)&(7,4) \end{array}$

Show code

## E - Make It Connected

You are given a simple undirected graph consisting of $$n$$ vertices. The graph doesn't contain self-loops, there is at most one edge between each pair of vertices. Your task is simple: make the graph connected

You can do the following operation any number of times (possibly zero):

• Choose a vertex $$u$$ arbitrarily
• For each vertex $$v$$ satisfying $$v\ne u$$ in the graph individually, if $$v$$ is adjacent to $$u$$, remove the edge between $$u$$ and $$v$$, otherwise add an edge between $$u$$ and $$v$$

Find the minimum number of operations required to make the graph connected. Also, find any sequence of operations with the minimum length that makes the graph connected

### Input

Each test contains multiple test cases. The first line contains a single integer $$t$$ ($$1\leq t\leq 800$$) — the number of test cases. The description of test cases follows

The first line of each test case contains a single integer $$n$$ ($$2\leq n\leq 4000$$) — the number of vertices in the graph

Then $$n$$ lines follow. The $$i$$-th row contains a binary string $$s_i$$ of length $$n$$, where $$s_{i,j}$$ is '1' if there is an edge between vertex $$i$$ and $$j$$ initially, otherwise $$s_{i,j}$$ is '0'

It is guaranteed that $$s_{i,i}$$ is always '0' and $$s_{i,j}=s_{j,i}$$ for $$1\leq i,j\leq n$$

It is guaranteed that the sum of $$n$$ over all test cases does not exceed $$4000$$

### Output

For each test case, in the first line, output an integer $$m$$ — the minimum number of operations required

If $$m$$ is greater than zero, then print an extra line consisting of $$m$$ integers — the vertices chosen in the operations in your solution. If there are multiple solutions with the minimum number of operations, print any

### Note

In the first test case, the graph is connected at the beginning, so the answer is $$0$$

In the second test case, if we do the operation with vertex $$1$$, we will get the following graph represented by an adjacency matrix:

$\begin{bmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{bmatrix}$

It's obvious that the graph above is connected

In the third test case, if we do the operation with vertex $$3$$ and $$4$$, we will get the following graph represented by an adjacency matrix:

$\begin{bmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{bmatrix}$

It's obvious that the graph above is connected, and it can be proven that we can't perform less than $$2$$ operations to make the graph connected

Show code

## F1 - Anti-median (Easy Version)

This is the easy version of the problem. The only difference between the two versions is the constraint on $$n$$. You can make hacks only if all versions of the problem are solved

Let's call an array $$a$$ of odd length $$2m+1$$ (with $$m \ge 1$$) bad, if element $$a_{m+1}$$ is equal to the median of this array. In other words, the array is bad if, after sorting it, the element at $$m+1$$-st position remains the same

Let's call a permutation $$p$$ of integers from $$1$$ to $$n$$ anti-median, if every its subarray of odd length $$\ge 3$$ is not bad

You are already given values of some elements of the permutation. Find the number of ways to set unknown values to obtain an anti-median permutation. As this number can be very large, find it modulo $$10^9+7$$

### Input

The first line contains a single integer $$t$$ ($$1 \le t \le 10^4$$) — the number of test cases. The description of test cases follows

The first line of each test case contains a single integer $$n$$ $$(2 \le n \le 1000)$$ — the length of the permutation

The second line of each test case contains $$n$$ integers $$p_1, p_2, \ldots, p_n$$ ($$1 \le p_i \le n$$, or $$p_i = -1$$) — the elements of the permutation. If $$p_i \neq -1$$, it's given, else it's unknown. It's guaranteed that if for some $$i \neq j$$ holds $$p_i \neq -1, p_j \neq -1$$, then $$p_i \neq p_j$$

It is guaranteed that the sum of $$n^2$$ over all test cases does not exceed $$10^6$$

### Output

For each test case, output a single integer — the number of ways to set unknown values to obtain an anti-median permutation, modulo $$10^9+7$$

### Note

In the first test case, both $$[1, 2]$$ and $$[2, 1]$$ are anti-median

In the second test case, permutations $$[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]$$ are anti-median. The remaining two permutations, $$[1, 2, 3]$$, $$[3, 2, 1]$$, are bad arrays on their own, as their median, $$2$$, is in their middle

In the third test case, $$[1, 2, 3, 4]$$ isn't anti-median, as it contains bad subarray $$[1, 2, 3]$$

In the fourth test case, the only anti-median array you can get is $$[5, 6, 3, 4, 1, 2]$$

Show code

## F2 - Anti-median (Hard Version)

This is the hard version of the problem. The only difference between the two versions is the constraint on $$n$$. You can make hacks only if all versions of the problem are solved

Let's call an array $$a$$ of odd length $$2m+1$$ (with $$m \ge 1$$) bad, if element $$a_{m+1}$$ is equal to the median of this array. In other words, the array is bad if, after sorting it, the element at $$m+1$$-st position remains the same

Let's call a permutation $$p$$ of integers from $$1$$ to $$n$$ anti-median, if every its subarray of odd length $$\ge 3$$ is not bad

You are already given values of some elements of the permutation. Find the number of ways to set unknown values to obtain an anti-median permutation. As this number can be very large, find it modulo $$10^9+7$$

### Input

The first line contains a single integer $$t$$ ($$1 \le t \le 10^4$$) — the number of test cases. The description of test cases follows

The first line of each test case contains a single integer $$n$$ $$(2 \le n \le 10^6)$$ — the length of the permutation

The second line of each test case contains $$n$$ integers $$p_1, p_2, \ldots, p_n$$ ($$1 \le p_i \le n$$, or $$p_i = -1$$) — the elements of the permutation. If $$p_i \neq -1$$, it's given, else it's unknown. It's guaranteed that if for some $$i \neq j$$ holds $$p_i \neq -1, p_j \neq -1$$, then $$p_i \neq p_j$$

It is guaranteed that the sum of $$n$$ over all test cases does not exceed $$10^6$$

### Output

For each test case, output a single integer — the number of ways to set unknown values to obtain an anti-median permutation, modulo $$10^9+7$$

### Note

In the first test case, both $$[1, 2]$$ and $$[2, 1]$$ are anti-median

In the second test case, permutations $$[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]$$ are anti-median. The remaining two permutations, $$[1, 2, 3]$$, $$[3, 2, 1]$$, are bad arrays on their own, as their median, $$2$$, is in their middle

In the third test case, $$[1, 2, 3, 4]$$ isn't anti-median, as it contains bad subarray $$[1, 2, 3]$$

In the fourth test case, the only anti-median array you can get is $$[5, 6, 3, 4, 1, 2]$$

Show code

## G - Centroid Guess

This in an interactive problem

There is an unknown tree consisting of $$n$$ nodes, which has exactly one centroid. You only know $$n$$ at first, and your task is to find the centroid of the tree

You can ask the distance between any two vertices for at most $$2\cdot10^5$$ times

Note that the interactor is not adaptive. That is, the tree is fixed in each test beforehand and does not depend on your queries

A vertex is called a centroid if its removal splits the tree into subtrees with at most $$\lfloor\frac{n}{2}\rfloor$$ vertices each

### Input

The only line of the input contains an integer $$n$$ ($$3\le n\le 7.5\cdot10^4$$) — the number of nodes in the tree

Interaction Start interaction by reading $$n$$

To ask a query about the distance between two nodes $$u, v$$ ($$1 \le u, v \le n$$), output "? u v"

If you determine that the centroid of the tree is $$x$$, use "! x" to report

After printing a query, do not forget to output the end of a line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages

Hacks are disabled in this problem

It's guaranteed that there are at most $$500$$ tests in this problem

### Note

Here is an image of the tree from the sample

Show code