1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Xor of Median (Easy Version)
Contest: Codeforces Round 997 (Div. 2)
Difficulty rating: 2700
Tags: bitmasks, brute force, combinatorics, dp, math

This is the easy version of the problem. The difference between the versions is that in this version, the constraints on $$$t$$$, $$$k$$$, and $$$m$$$ are lower. You can hack only if you solved all versions of this problem.

A sequence $$$a$$$ of $$$n$$$ integers is called good if the following condition holds:

- Let $$$\text{cnt}_x$$$ be the number of occurrences of $$$x$$$ in sequence $$$a$$$. For all pairs $$$0 \le i < j < m$$$, at least one of the following has to be true: $$$\text{cnt}_i = 0$$$, $$$\text{cnt}_j = 0$$$, or $$$\text{cnt}_i \le \text{cnt}_j$$$. In other words, if both $$$i$$$ and $$$j$$$ are present in sequence $$$a$$$, then the number of occurrences of $$$i$$$ in $$$a$$$ is less than or equal to the number of occurrences of $$$j$$$ in $$$a$$$.

You are given integers $$$n$$$ and $$$m$$$. Calculate the value of the bitwise XOR of the median$$$^{\text{∗}}$$$ of all good sequences $$$a$$$ of length $$$n$$$ with $$$0\le a_i < m$$$.

Note that the value of $$$n$$$ can be very large, so you are given its binary representation instead.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 50$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$k$$$ and $$$m$$$ ($$$1 \le k \le 200$$$, $$$1 \le m \le 500$$$) — the number of bits in $$$n$$$ and the upper bound on the elements in sequence $$$a$$$.

The second line of each test case contains a binary string of length $$$k$$$ — the binary representation of $$$n$$$ with no leading zeros.

It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$200$$$.

Output format:
For each test case, output a single integer representing the bitwise XOR of the median of all good sequences $$$a$$$ of length $$$n$$$ where $$$0\le a_i < m$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example, $$$n = 10_2 = 2$$$ and $$$m = 3$$$. All possible sequences with elements less than $$$m$$$ are: $$$[0, 0]$$$, $$$[0, 1]$$$, $$$[0, 2]$$$, $$$[1, 0]$$$, $$$[1, 1]$$$, $$$[1, 2]$$$, $$$[2, 0]$$$, $$$[2, 1]$$$, $$$[2, 2]$$$. All of them are good, so the answer is: $$$0 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 \oplus 1 \oplus 2 = 3$$$.

In the second example, $$$n = 11_2 = 3$$$ and $$$m = 3$$$. Some good sequences are $$$[2, 2, 2]$$$, $$$[1, 0, 1]$$$, and $$$[2, 0, 1]$$$. However, a sequence $$$[2, 0, 0]$$$ is not good, because $$$\text{cnt}_0 = 2$$$, $$$\text{cnt}_2 = 1$$$. Therefore, if we set $$$i = 0$$$ and $$$j = 2$$$, $$$i < j$$$ holds, but $$$\text{cnt}_i \le \text{cnt}_j$$$ does not.

Example input:
6
2 3
10
2 3
11
5 1
11101
7 9
1101011
17 34
11001010001010010
1 500
1

Example output:
3
2
0
8
32
0

Editorial:
Xor of Median (Hard Version)
Contest: Codeforces Round 997 (Div. 2)
Difficulty rating: 3000
Tags: bitmasks, brute force, combinatorics, dp, math

This is the hard version of the problem. The difference between the versions is that in this version, the constraints on $$$t$$$, $$$k$$$, and $$$m$$$ are higher. You can hack only if you solved all versions of this problem.

A sequence $$$a$$$ of $$$n$$$ integers is called good if the following condition holds:

- Let $$$\text{cnt}_x$$$ be the number of occurrences of $$$x$$$ in sequence $$$a$$$. For all pairs $$$0 \le i < j < m$$$, at least one of the following has to be true: $$$\text{cnt}_i = 0$$$, $$$\text{cnt}_j = 0$$$, or $$$\text{cnt}_i \le \text{cnt}_j$$$. In other words, if both $$$i$$$ and $$$j$$$ are present in sequence $$$a$$$, then the number of occurrences of $$$i$$$ in $$$a$$$ is less than or equal to the number of occurrences of $$$j$$$ in $$$a$$$.

You are given integers $$$n$$$ and $$$m$$$. Calculate the value of the bitwise XOR of the median$$$^{\text{∗}}$$$ of all good sequences $$$a$$$ of length $$$n$$$ with $$$0\le a_i < m$$$.

Note that the value of $$$n$$$ can be very large, so you are given its binary representation instead.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$k$$$ and $$$m$$$ ($$$1 \le k \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — the number of bits in $$$n$$$ and the upper bound on the elements in sequence $$$a$$$.

The second line of each test case contains a binary string of length $$$k$$$ — the binary representation of $$$n$$$ with no leading zeros.

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

Output format:
For each test case, output a single integer representing the bitwise XOR of the median of all good sequences $$$a$$$ of length $$$n$$$ where $$$0\le a_i < m$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example, $$$n = 10_2 = 2$$$ and $$$m = 3$$$. All possible sequences with elements less than $$$m$$$ are: $$$[0, 0]$$$, $$$[0, 1]$$$, $$$[0, 2]$$$, $$$[1, 0]$$$, $$$[1, 1]$$$, $$$[1, 2]$$$, $$$[2, 0]$$$, $$$[2, 1]$$$, $$$[2, 2]$$$. All of them are good, so the answer is: $$$0 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 \oplus 1 \oplus 2 = 3$$$.

In the second example, $$$n = 11_2 = 3$$$ and $$$m = 3$$$. Some good sequences are $$$[2, 2, 2]$$$, $$$[1, 0, 1]$$$, and $$$[2, 0, 1]$$$. However, a sequence $$$[2, 0, 0]$$$ is not good, because $$$\text{cnt}_0 = 2$$$, $$$\text{cnt}_2 = 1$$$. Therefore, if we set $$$i = 0$$$ and $$$j = 2$$$, $$$i < j$$$ holds, but $$$\text{cnt}_i \le \text{cnt}_j$$$ does not.

Example input:
6
2 3
10
2 3
11
5 1
11101
7 9
1101011
17 34
11001010001010010
1 1000000000
1

Example output:
3
2
0
8
32
0

Editorial:
Adjacent Digit Sums
Contest: Codeforces Round 1004 (Div. 2)
Difficulty rating: 800
Tags: brute force, constructive algorithms, math

Given two numbers $$$x, y$$$. You need to determine if there exists an integer $$$n$$$ such that $$$S(n) = x$$$, $$$S(n + 1) = y$$$.

Here, $$$S(a)$$$ denotes the sum of the digits of the number $$$a$$$ in the decimal numeral system.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$x, y$$$ ($$$1 \le x \le 1000, 1 \le y \le 1000$$$).

Output format:
For each test case, print "NO" if a suitable $$$n$$$ does not exist. Otherwise, output "YES".

You can output each letter in any case (for example, "YES", "Yes", "yes", "yEs", "yEs" will be recognized as a positive answer).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, for example, $$$n = 100$$$ works. $$$S(100) = 1$$$, $$$S(101) = 2$$$.

In the second test case, it can be shown that $$$S(n) \neq S(n+1)$$$ for all $$$n$$$; therefore, the answer is No.

In the fourth test case, $$$n = 10^{111}-1$$$ works, which is a number consisting of $$$111$$$ digits of $$$9$$$.

Example input:
7
1 2
77 77
997 999
999 1
1000 1
1 11
18 1

Example output:
Yes
No
No
Yes
No
No
Yes

Editorial:
Let's look at the last digit of the number $$$n$$$. If it is not equal to $$$9$$$, then in the number $$$n+1$$$, this last digit will be increased by $$$1$$$, while the rest of the number will remain unchanged. Thus, for such $$$n$$$, we have $$$S(n+1) = S(n) + 1$$$.
In general, if the number $$$n$$$ ends with $$$k$$$ consecutive digits of $$$9$$$, then it turns out that $$$S(n+1) = S(n) + 1 - 9k$$$, since all these $$$9$$$s will be replaced by $$$0$$$s after adding one to the number $$$n$$$.
Therefore, if there does not exist an integer $$$k \geq 0$$$ such that $$$y = x + 1 - 9k$$$, then the answer is definitely No. Otherwise, it is easy to see that the answer is definitely Yes.
One of the suitable numbers is: $$$n = \underbrace{11 \ldots 1}_{x-9k}\underbrace{99 \ldots 9}_{k}$$$. Then, $$$S(n) = x - 9k + 9k = x$$$.
And $$$n + 1 = \underbrace{11 \ldots 1}_{x-9k-1}2\underbrace{00 \ldots 0}_{k}$$$. Thus, $$$S(n+1) = x - 9k - 1 + 2 = x + 1 - 9k$$$.
Therefore, to solve the problem, we need to check whether the number $$$\frac{x + 1 - y}{9}$$$ is an integer and non-negative.
Simple Palindrome
Contest: Codeforces Round 972 (Div. 2)
Difficulty rating: 900
Tags: combinatorics, constructive algorithms, greedy, math

Narek has to spend 2 hours with some 2-year-old kids at the kindergarten. He wants to teach them competitive programming, and their first lesson is about palindromes.

Narek found out that the kids only know the vowels of the English alphabet (the letters $$$\mathtt{a}$$$, $$$\mathtt{e}$$$, $$$\mathtt{i}$$$, $$$\mathtt{o}$$$, and $$$\mathtt{u}$$$), so Narek needs to make a string that consists of vowels only. After making the string, he'll ask the kids to count the number of subsequences that are palindromes. Narek wants to keep it simple, so he's looking for a string such that the amount of palindrome subsequences is minimal.

Help Narek find a string of length $$$n$$$, consisting of lowercase English vowels only (letters $$$\mathtt{a}$$$, $$$\mathtt{e}$$$, $$$\mathtt{i}$$$, $$$\mathtt{o}$$$, and $$$\mathtt{u}$$$), which minimizes the amount of palindrome$$$^{\dagger}$$$ subsequences$$$^{\ddagger}$$$ in it.

$$$^{\dagger}$$$ A string is called a palindrome if it reads the same from left to right and from right to left.

$$$^{\ddagger}$$$ String $$$t$$$ is a subsequence of string $$$s$$$ if $$$t$$$ can be obtained from $$$s$$$ by removing several (possibly, zero or all) characters from $$$s$$$ and concatenating the remaining ones, without changing their order. For example, $$$\mathtt{odocs}$$$ is a subsequence of $$$\texttt{c}{\color{red}{\texttt{od}}}\texttt{ef}{\color{red}{\texttt{o}}}\texttt{r}{\color{red}{\texttt{c}}}\texttt{e}{\color{red}{\texttt{s}}}$$$.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. Subsequently, the description of each test case follows.

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the size of the string.

Output format:
For each test case, output any string of length $$$n$$$ that satisfies the above conditions.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, $$$\texttt{uo}$$$ has only three palindrome subsequences: $$$\texttt{u}$$$, $$$\texttt{o}$$$, and the empty string. It can be shown that there is no better answer.

In the third example, $$$\texttt{oeiiua}$$$ has only eight palindrome subsequences: $$$\texttt{o}$$$, $$$\texttt{e}$$$, $$$\texttt{i}$$$, $$$\texttt{i}$$$, $$$\texttt{u}$$$, $$$\texttt{a}$$$, $$$\texttt{ii}$$$, and the empty string. It can be shown that there is no better answer.

Example input:
3
2
3
6

Example output:
uo
iae
oeiiua

Editorial:
Alter the GCD
Contest: Codeforces Round 972 (Div. 2)
Difficulty rating: 2400
Tags: binary search, brute force, data structures, divide and conquer, implementation, number theory

You are given two arrays $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$.

You must perform the following operation exactly once:

- choose any indices $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$;
- swap $$$a_i$$$ and $$$b_i$$$ for all $$$i$$$ such that $$$l \leq i \leq r$$$.

Find the maximum possible value of $$$\text{gcd}(a_1, a_2, \ldots, a_n) + \text{gcd}(b_1, b_2, \ldots, b_n)$$$ after performing the operation exactly once. Also find the number of distinct pairs $$$(l, r)$$$ which achieve the maximum value.

Input format:
In the first line of the input, you are given a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$), the number of test cases. Then the description of each test case follows.

In the first line of each test case, you are given a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), representing the number of integers in each array.

In the next line, you are given $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

In the last line, you are given $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the elements of the array $$$b$$$.

The sum of values of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output format:
For each test case, output a line with two integers: the maximum value of $$$\text{gcd}(a_1, a_2, \ldots, a_n) + \text{gcd}(b_1, b_2, \ldots, b_n)$$$ after performing the operation exactly once, and the number of ways.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first, third, and fourth test cases, there's no way to achieve a higher GCD than $$$1$$$ in any of the arrays, so the answer is $$$1 + 1 = 2$$$. Any pair $$$(l, r)$$$ achieves the same result; for example, in the first test case there are $$$36$$$ such pairs.

In the last test case, you must choose $$$l = 1$$$, $$$r = 2$$$ to maximize the answer. In this case, the GCD of the first array is $$$5$$$, and the GCD of the second array is $$$1$$$, so the answer is $$$5 + 1 = 6$$$, and the number of ways is $$$1$$$.

Example input:
5
8
11 4 16 17 3 24 25 8
8 10 4 21 17 18 25 21
4
6 4 24 13
15 3 1 14
2
13 14
5 8
8
20 17 15 11 21 10 3 7
9 9 4 20 14 9 13 1
2
18 13
15 20

Example output:
2 36
3 2
2 3
2 36
6 1

Editorial:
Subtangle Game (Easy Version)
Contest: Codeforces Round 972 (Div. 2)
Difficulty rating: 2100
Tags: dp, games, greedy, implementation

This is the easy version of the problem. The differences between the two versions are the constraints on all the variables. You can make hacks only if both versions of the problem are solved.

Tsovak and Narek are playing a game. They have an array $$$a$$$ and a matrix $$$b$$$ of integers with $$$n$$$ rows and $$$m$$$ columns, numbered from $$$1$$$. The cell in the $$$i$$$-th row and the $$$j$$$-th column is $$$(i, j)$$$.

They are looking for the elements of $$$a$$$ in turns; Tsovak starts first. Each time a player looks for a cell in the matrix containing the current element of $$$a$$$ (Tsovak looks for the first, then Narek looks for the second, etc.). Let's say a player has chosen the cell $$$(r, c)$$$. The next player has to choose his cell in the submatrix starting at $$$(r + 1, c + 1)$$$ and ending in $$$(n, m)$$$ (the submatrix can be empty if $$$r=n$$$ or $$$c=m$$$). If a player cannot find such a cell (or the remaining submatrix is empty) or the array ends (the previous player has chosen the last element), then he loses.

Your task is to determine the winner if the players play optimally.

Input format:
The first line of the input contains $$$t$$$ ($$$1 \le t \le 300$$$) – the number of test cases.

The first line of each test case contains three integers $$$l$$$, $$$n$$$, and $$$m$$$ ($$$1 \le l, n, m \le 300$$$) – the size of the array and the sizes of the matrix.

The second line contains $$$l$$$ integers $$$a_1, a_2, a_3, \ldots a_l$$$ ($$$1 \le a_i \le \min(7, n \cdot m)$$$) – the elements of the array $$$a$$$.

The $$$i$$$-th of the last $$$n$$$ lines contains $$$m$$$ integers $$$b_{i,1}, b_{i,2}, b_{i,3}, \ldots b_{i,m}$$$ ($$$1 \le b_{i,j} \le \min(7, n \cdot m)$$$) – representing the $$$i$$$-th row of the matrix.

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

It is guaranteed that the sum of $$$l$$$ over all test cases does not exceed $$$300$$$.

Output format:
You should output $$$t$$$ lines, the $$$i$$$-th of them containing a character representing the answer of the $$$i$$$-th test case: "T" if Tsovak wins or "N", otherwise (without quotes).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, Tsovak starts by looking for $$$1$$$. There is only one occurrence of $$$1$$$ at $$$(1,1)$$$, so he chooses it. Then Narek needs to look for $$$2$$$ in the submatrix of $$$(2, 2)$$$, which consists of just the last two elements: $$$5$$$ and $$$2$$$. He chooses $$$2$$$, and then Tsovak loses since the array has ended.

In the second example, Tsovak needs to choose $$$1$$$. There is a $$$1$$$ at the cell $$$(n,m)$$$, so he chooses that cell. Then, since the submatrix of $$$(n + 1, m + 1)$$$ is empty, Narek cannot find $$$2$$$, so he loses.

Example input:
3
2 2 3
1 2
1 3 5
4 5 2
2 2 4
1 2
1 1 3 2
4 2 5 1
2 4 2
1 2
3 4
5 5
5 5
5 5

Example output:
N
T
N

Editorial:
King Keykhosrow's Mystery
Contest: Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
Difficulty rating: 800
Tags: brute force, chinese remainder theorem, math, number theory

There is a tale about the wise King Keykhosrow who owned a grand treasury filled with treasures from across the Persian Empire. However, to prevent theft and ensure the safety of his wealth, King Keykhosrow's vault was sealed with a magical lock that could only be opened by solving a riddle.

The riddle involves two sacred numbers $$$a$$$ and $$$b$$$. To unlock the vault, the challenger must determine the smallest key number $$$m$$$ that satisfies two conditions:

- $$$m$$$ must be greater than or equal to at least one of $$$a$$$ and $$$b$$$.
- The remainder when $$$m$$$ is divided by $$$a$$$ must be equal to the remainder when $$$m$$$ is divided by $$$b$$$.

Only by finding the smallest correct value of $$$m$$$ can one unlock the vault and access the legendary treasures!

Input format:
The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$), the number of test cases.

Each test case consists of a single line containing two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq 1000$$$).

Output format:
For each test case, print the smallest integer $$$m$$$ that satisfies the conditions above.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can see that:

- $$$4 \bmod 4 = 0$$$ but $$$4 \bmod 6 = 4$$$
- $$$5 \bmod 4 = 1$$$ but $$$5 \bmod 6 = 5$$$
- $$$6 \bmod 4 = 2$$$ but $$$6 \bmod 6 = 0$$$
- $$$7 \bmod 4 = 3$$$ but $$$7 \bmod 6 = 1$$$
- $$$8 \bmod 4 = 0$$$ but $$$8 \bmod 6 = 2$$$
- $$$9 \bmod 4 = 1$$$ but $$$9 \bmod 6 = 3$$$
- $$$10 \bmod 4 = 2$$$ but $$$10 \bmod 6 = 4$$$
- $$$11 \bmod 4 = 3$$$ but $$$11 \bmod 6 = 5$$$

Example input:
2
4 6
472 896

Example output:
12
52864

Editorial:
Trapped in the Witch's Labyrinth
Contest: Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, dfs and similar, graphs, implementation

In the fourth labor of Rostam, the legendary hero from the Shahnameh, an old witch has created a magical maze to trap him. The maze is a rectangular grid consisting of $$$n$$$ rows and $$$m$$$ columns. Each cell in the maze points in a specific direction: up, down, left, or right. The witch has enchanted Rostam so that whenever he is in a cell, he will move to the next cell in the direction indicated by that cell.

If Rostam eventually exits the maze, he will be freed from the witch's enchantment and will defeat her. However, if he remains trapped within the maze forever, he will never escape.

The witch has not yet determined the directions for all the cells. She wants to assign directions to the unspecified cells in such a way that the number of starting cells from which Rostam will be trapped forever is maximized. Your task is to find the maximum number of starting cells which make Rostam trapped.

Input format:
The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$), the number of test cases.

For each test case:

- The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 1000$$$), representing the number of rows and columns in the maze.
- Each of the next $$$n$$$ lines contains a string of $$$m$$$ characters representing the directions in the maze. Each character is one of the following:   U (up)  D (down)  L (left)  R (right)  ? (unspecified direction)

It's guaranteed that the sum of $$$n \cdot m$$$ over all test cases is at most $$$10^6$$$.

Output format:
For each test case, print a single integer, the maximum number of starting cells from which Rostam will be trapped forever after assigning directions to the unspecified cells optimally.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, all of the cells will be good no matter what you do.

In the second test case, if you assign the ?s like the picture below, all of the cells will be bad:

In the third test case, if you assign the ?s like the picture below, you will have $$$5$$$ bad cells (red-shaded cells):

Example input:
3
3 3
UUU
L?R
DDD
2 3
???
???
3 3
?U?
R?L
RDL

Example output:
0
6
5

Editorial:
Simurgh's Watch (Easy Version)
Contest: Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: constructive algorithms, greedy, implementation, sortings

The only difference between the two versions of the problem is whether overlaps are considered at all points or only at integer points.

The legendary Simurgh, a mythical bird, is responsible for keeping watch over vast lands, and for this purpose, she has enlisted $$$n$$$ vigilant warriors. Each warrior is alert during a specific time segment $$$[l_i, r_i]$$$, where $$$l_i$$$ is the start time (included) and $$$r_i$$$ is the end time (included), both positive integers.

One of Simurgh's trusted advisors, Zal, is concerned that if multiple warriors are stationed at the same time and all wear the same color, the distinction between them might be lost, causing confusion in the watch. To prevent this, whenever multiple warriors are on guard at the same moment (which can be non-integer), there must be at least one color which is worn by exactly one warrior.

So the task is to determine the minimum number of colors required and assign a color $$$c_i$$$ to each warrior's segment $$$[l_i, r_i]$$$ such that, for every (real) time $$$t$$$ contained in at least one segment, there exists one color which belongs to exactly one segment containing $$$t$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

For each test case:

- The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of warriors stationed by Simurgh.
- The next $$$n$$$ lines each contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^9$$$) — the start and end times of the warrior's watch segment.

The sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case:

- Output the minimum number of colors $$$k$$$ needed.
- Then, output a line of $$$n$$$ integers $$$c_i$$$ ($$$1 \leq c_i \leq k$$$), where each $$$c_i$$$ is the color assigned to the $$$i$$$-th warrior.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
We can represent each warrior's watch segment as an interval on the X-axis;

In test case 1, we have two independent intervals, which can be colored with the same color.

In test case 2, point 2 is common to two intervals, meaning we cannot color them with the same color.

In test case 3, the intervals can be colored as shown below (intervals are colored with the selected color; areas are colored if this color occurs exactly once at this point in time):

In test case 4, the intervals can be colored as shown below:

In test case 5, the intervals can be colored as shown below. The image on the right demonstrates an example of incorrect coloring for this test case; there is no unique color at the moment $$$5.5$$$:

Example input:
5
2
1 2
3 4
2
1 2
2 3
3
1 4
2 5
3 6
5
1 4
2 8
3 7
5 10
6 9
5
1 5
2 6
3 7
4 7
6 7

Example output:
1
1 1
2
1 2
2
1 2 1
3
2 3 1 2 1
3
2 1 3 1 1

Editorial: