TheForces Round #43 (DIV2-Forces)
A. Mystic Quest
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer $$$n$$$. Your task is to count how many integers $$$x$$$ ($$$1 \le x \le n$$$) are mystic numbers. A number $$$x$$$ is called mystic if $$$$$$x,\ x^x,\ x^{(x^x)},\ x^{(x^{(x^x)})},\ x^{(x^{(x^{(x^x)})})},\ \ldots$$$$$$ are all perfect squares.

A perfect square is an integer that is the square of an integer. For example, $$$9 = 3^2$$$ is a perfect square, but $$$8$$$ and $$$14$$$ are not.

Input

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le $$$ $$$10 ^ 3$$$). The description of the test cases follows.

A single line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{6}$$$).

Output

For each test case, output a single integer — the number of mystic numbers.

Example
Input
2
2
5
Output
1
2
Note

In the first test case, there is exactly one value of $$$x$$$, which is $$$1$$$, that satisfies the conditions.

B. Permutation We Stand
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer $$$n$$$.

Your task is to find a permutation $$$p$$$ of size $$$n$$$ that satisfies the following conditions:

  • For every $$$i$$$ ($$$1 \le i \le n - 2$$$), $$$\gcd(p_i, p_{i+1}) = 1$$$.
  • $$$\gcd(p_{n - 1}, p_n) \neq 1$$$.

Here $$$\operatorname{gcd}$$$ denotes the greatest common divisor.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ and $$$[1,3,4]$$$ are not permutations.

Output any valid permutation that satisfies these conditions. If a valid permutation does not exist, output $$$-1$$$ instead.

Input

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le $$$ $$$10 ^ 3$$$). The description of the test cases follows.

A single line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^{5}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10 ^ 5$$$.

Output

For each test case, output any valid permutation. If multiple solutions exist, output any one of them. If no valid permutations exist, output $$$-1$$$ instead.

Example
Input
2
2
6
Output
-1
4 1 2 5 6 3

C1. Colorful Subarrays (Easy Version)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem. The only difference is that in this version $$$k = 3$$$ and sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

An array is called colorful array if and only if all its numbers are distinct.

You are given three integers $$$n$$$, $$$m$$$, and $$$k$$$.

Your task is to construct an array $$$a$$$ of size $$$n$$$ satisfying:

  • $$$1 \le a_i \le k$$$.
  • The count of colorful subarrays among all $$$\frac{n(n+1)}{2}$$$ subarrays of $$$a$$$ is exactly $$$m$$$.
Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

Each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n \leq 5000$$$, $$$0 \leq m \leq \frac{n(n+1)}{2}$$$, $$$\bf{k=3}$$$).

NOTE: It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

If such an array doesn't exist, output $$$-1$$$.

Otherwise, output $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ in a new line.

Example
Input
4
1 1 3
2 3 3
2 1 3
4 5 3
Output
1
1 2
-1
2 1 1 1
Note

In the fourth test case, $$$a=[2,1,1,1]$$$ has exactly $$$5$$$ colorful subarrays $$$[a_1]$$$, $$$[a_2]$$$, $$$[a_3]$$$, $$$[a_4]$$$, and $$$[a_1,a_2]$$$.

C2. Colorful Subarrays (Hard Version)
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The only difference is that in this version $$${1 \leq k \leq 5000}$$$ and sum of $$$n$$$ over all test cases does not exceed $$$5\times 10^6$$$.

An array is called colorful array if and only if all its numbers are distinct.

You are given three integers $$$n$$$, $$$m$$$, and $$$k$$$.

Your task is to construct an array $$$a$$$ of size $$$n$$$ satisfying:

  • $$$1 \le a_i \le k$$$.
  • The count of colorful subarrays among all $$$\frac{n(n+1)}{2}$$$ subarrays of $$$a$$$ is exactly $$$m$$$.
Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

Each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n \leq 5000$$$, $$$0 \leq m \leq \frac{n(n+1)}{2}$$$, $$$\bf{1 \leq k \leq 5000}$$$).

NOTE: It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\times 10^6$$$.

Output

If such an array doesn't exist, output $$$-1$$$.

Otherwise, output $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ in a new line.

Example
Input
6
1 1 3
2 3 3
2 1 3
4 5 3
4 10 7
4 6 5
Output
1 
2 1
-1
2 1 1 1
4 5 6 7
1 4 4 5
Note

In the fourth test case, $$$a=[2,1,1,1]$$$ has exactly $$$5$$$ colorful subarrays $$$[a_1]$$$, $$$[a_2]$$$, $$$[a_3]$$$, $$$[a_4]$$$, and $$$[a_1,a_2]$$$.

D. Simplest Fractions
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A fraction $$$\frac{a}{b}$$$ ($$$a$$$ and $$$b$$$ are positive integers) is called a simplest fraction if and only if it satisfies the following conditions:

  • $$$a \gt 0$$$, $$$b \gt 1$$$.
  • $$$\gcd(a, b) = 1$$$.

Here $$$\operatorname{gcd}$$$ denotes the greatest common divisor.

You are given two integers $$$l$$$ and $$$r$$$. Find the number of simplest fractions $$$\frac{a}{b}$$$ such that $$$l \le a + b \le r$$$.

Input

The first line of the input will contain a single integer $$$t$$$ $$$(1\le t\le 10^5)$$$, the total number of test cases.

Each test case will contain two integers $$$l$$$ and $$$r$$$ $$$(1 \le l \le r \le 10^{6})$$$.

Note there is no constraint on the sum of $$$l$$$ and $$$r$$$ over all test cases.

Output

Print in a new line  — the number of simplest fractions $$$\frac{a}{b}$$$ that satisfy the condition above.

Example
Input
2
1 3
4 5
Output
1
4
Note

In the first test case, only $$$\frac{1}{2}$$$ satisfies the condition.

In the second test case, $$$\frac{1}{3}$$$, $$$\frac{1}{4}$$$, $$$\frac{2}{3}$$$, and $$$\frac{3}{2}$$$ satisfy the condition.

E. Empty Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes.

Your task is to delete the entire tree with the following operation:

  • Choose any two connected nodes $$$x$$$ and $$$y$$$ $$$(1 \le x,y \le n$$$, $$$x \neq y)$$$ which have not been deleted. Then, delete all the nodes on the simple path between $$$x$$$ and $$$y$$$ (inclusive), and delete all the edges connected to these nodes.

If it is possible to delete the entire tree with operations, output any scheme. Otherwise, output $$$-1$$$ instead.

Input

The input consists of multiple test cases. The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$), the number of test cases.

The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 2000)$$$ — the number of vertices in the tree.

The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), indicating an edge between nodes $$$u$$$ and $$$v$$$.

It is guaranteed that the given input forms a tree.

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

Output

If it is possible to delete the entire tree with operations:

  • The first line of the output contains an integer $$$k$$$ $$$(1 \le k \le \lfloor \frac{n}{2} \lfloor)$$$  — the number of operations.
  • The $$$i$$$-th line contains $$$x_i$$$ and $$$y_i$$$ $$$(1 \leq x_i, y_i \leq n; x_i \neq y_i)$$$, where $$$x_i$$$ and $$$y_i$$$ denote the chosen nodes in the $$$i$$$-th operation.

Otherwise, output $$$-1$$$ instead.

Example
Input
4
3
1 2
2 3
4
1 2
2 3
2 4
5
1 2
1 3
2 4
2 5
7
1 2
1 3
1 4
4 5
5 6
5 7
Output
1
3 1
-1
2
4 5
1 3
-1
Note

In the second test case, no matter which $$$2$$$ nodes you choose at first, there will always be at least $$$1$$$ node that will be disconnected from the tree and can not be deleted any more.

In the third test case, select nodes $$$4$$$ and $$$5$$$ and delete every node in the simple path from $$$4$$$ to $$$5$$$, along with the edges connected to those nodes. Repeat the same process for nodes $$$1$$$ and $$$3$$$ (The nodes and edges to be deleted are marked in red).

F. Equal Node Sum
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You're given a rooted tree with $$$n$$$ vertices. The root node is $$$1$$$. You can set the weight of each edge to either $$$0$$$ or $$$1$$$. We call the sum value of node $$$i$$$ the sum of the weights of all edges incident to it.

Count the number of different assignments of edge weights that satisfy the following condition.

  • For each non-leaf node$$$^\dagger$$$, its sum value is equal to the sum value of every other non-leaf node.

Since the answer may be large, output the answer modulo $$$998\,244\,353$$$.

$$$^\dagger$$$ A node is called a non-leaf node if and only if it is the root node $$$1$$$ or there are at least $$$2$$$ edges incident to it.

Input

The input consists of multiple test cases. The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$), the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$), the number of nodes in the tree.
  • The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), indicating an edge between nodes $$$u$$$ and $$$v$$$. It is guaranteed that the given input forms a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer representing the number of different trees satisfying the given condition, modulo $$$998\,244\,353$$$.

Example
Input
5
3
1 2
1 3
3
1 2
2 3
4
1 4
2 4
3 1
6
1 4
2 3
3 6
4 3
5 2
8
1 2
2 4
3 4
4 8
5 1
6 4
7 3
Output
4
2
4
3
6
Note

In the first test case, there is only one non-leaf node: node $$$1$$$. You can set edge weights arbitrarily; thus, there are $$$4$$$ different assignments of edge weights.

In the second test case, there are two non-leaf nodes: nodes $$$1$$$ and $$$2$$$. There are $$$2$$$ valid assignments as shown below.

The two valid assignments.