1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Two Permutations
Contest: Codeforces Round 131 (Div. 1)
Difficulty rating: 2700
Tags: data structures, hashing, strings

Rubik is very keen on number permutations.

A permutation a with length n is a sequence, consisting of n different numbers from 1 to n. Element number i (1 ≤ i ≤ n) of this permutation will be denoted as ai.

Furik decided to make a present to Rubik and came up with a new problem on permutations. Furik tells Rubik two number permutations: permutation a with length n and permutation b with length m. Rubik must give an answer to the problem: how many distinct integers d exist, such that sequence c (c1 = a1 + d, c2 = a2 + d, ..., cn = an + d) of length n is a subsequence of b.

Sequence a is a subsequence of sequence b, if there are such indices i1, i2, ..., in (1 ≤ i1 < i2 < ... < in ≤ m), that a1 = bi1, a2 = bi2, ..., an = bin, where n is the length of sequence a, and m is the length of sequence b.

You are given permutations a and b, help Rubik solve the given problem.

Input format:
The first line contains two integers n and m (1 ≤ n ≤ m ≤ 200000) — the sizes of the given permutations. The second line contains n distinct integers — permutation a, the third line contains m distinct integers — permutation b. Numbers on the lines are separated by spaces.

Output format:
On a single line print the answer to the problem.

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

Example input:
1 1
1
1

Example output:
1

Example input:
1 2
1
2 1

Example output:
2

Editorial:
Зингер | color
Contest: VK Cup 2021 - Квалификация (Engine)
Tags: *special, implementation

Немногие знают, что сотрудники ВКонтакте могут менять цвет подсветки в куполе знаменитого Дома Зингера, где расположена штаб-квартира ВКонтакте. Для этого нужно всего лишь отправить сообщение с цветом в специальный чат «Зингер | color», а бот его распознает и сменит подсветку. При этом на время городских мероприятий смена цвета блокируется.

Формально, бот обрабатывает три типа сообщений:

- lock: заблокировать изменение цвета. Если оно и так заблокировано на данный момент, сообщение игнорируется.
- unlock: разблокировать изменение цвета. Если оно и так разблокировано на данный момент, сообщение игнорируется.
- red / orange / yellow / green / blue / indigo / violet: изменить цвет купола на заданный, если изменение цвета на данный момент не заблокировано.

Вам дана история сообщений, полученных ботом, в хронологическом порядке. Считайте, что перед получением первого сообщения купол подсвечивается голубым (blue), а изменение цвета не заблокировано.

Определите, какой цвет будет у купола Дома Зингера после обработки этих сообщений.

Input format:
В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — число сообщений, полученных ботом.

В следующих $$$n$$$ строках заданы сообщения, полученные ботом, в хронологическом порядке, по одному сообщению в строке. Каждое сообщение — строка из следующего набора: lock, unlock, red, orange, yellow, green, blue, indigo, violet.

Output format:
Выведите цвет купола после обработки сообщений ботом.

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

Example input:
7
red
violet
unlock
red
orange
lock
indigo

Example output:
orange

Example input:
5
lock
unlock
lock
unlock
unlock

Example output:
blue

Editorial:
Для решения этой задачи достаточно промоделировать операции, описанные в условии. Например, можно использовать переменную color типа string, содержащую текущий цвет купола, и переменную locked типа boolean, обозначающую, заблокировано ли сейчас изменение цвета.
Пример решения на Python:
Мониторинг
Contest: VK Cup 2021 - Квалификация (Engine)
Tags: *special, *special

ВКонтакте открыла второй штаб в Санкт-Петербурге! Вы не преминули возможностью сменить обстановку и решили переехать из офиса в Доме Зингера в офис на Красном мосту.

Для комфортной работы вам потребуются два монитора с одинаковой высотой, чтобы изображение на них выглядело единым целым. На складе офиса на Красном мосту есть $$$n$$$ мониторов, $$$i$$$-й из них имеет ширину $$$w_i$$$ и высоту $$$h_i$$$. Любой монитор можно повернуть на 90 градусов, и тогда он будет иметь ширину $$$h_i$$$ и высоту $$$w_i$$$.

Назовём неупорядоченную пару из двух различных мониторов подходящей, если можно их повернуть так, чтобы они имели одинаковую высоту. Любой из мониторов в паре можно как повернуть относительно исходной ориентации, так и не поворачивать.

Подсчитайте подходящие пары мониторов.

Input format:
В первой строке задано одно целое число $$$n$$$ — число мониторов на складе.

В каждой из следующих $$$n$$$ строк заданы два целых числа $$$w_i$$$ и $$$h_i$$$ ($$$1 \le w_i, h_i \le 10^9$$$) — ширина и высота $$$i$$$-го монитора. Обратите внимание, что мониторы могут быть квадратными ($$$w_i = h_i$$$), а размеры разных мониторов могут совпадать.

В этой версии задачи $$$2 \le n \le 10^3$$$.

Output format:
Выведите число подходящих пар мониторов.

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

Note:
В первом примере подходящими являются пары мониторов с номерами $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(3, 4)$$$, $$$(4, 5)$$$.

Во втором примере все пары мониторов — подходящие.

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

Example output:
5

Example input:
7
10 10
10 20
20 10
10 20
10 20
10 10
20 10

Example output:
21

Editorial:
В первой подзадаче достаточно перебрать все пары мониторов и проверить заданное условие. Пара мониторов $$$(i, j)$$$ подходящая, если любое из чисел $$$w_i, h_i$$$ равно любому из чисел $$$w_j, h_j$$$.
Пример решения на Python:
Такой алгоритм имеет сложность $$$O(n^2)$$$ и недостаточно эффективен для второй подзадачи.
Сортировка слиянием
Contest: VK Cup 2021 - Квалификация (Engine)
Tags: *special

Рассмотрим следующий код сортировки слиянием на языке Python:

Как можно заметить, этот код использует логирование — важнейший инструмент разработки.

Старший разработчик ВКонтакте Вася сгенерировал перестановку $$$a$$$ (массив из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$), дал её на вход функции sort и получил на выходе строку $$$s$$$. На следующий день строку $$$s$$$ Вася нашёл, а перестановка $$$a$$$ потерялась.

Вася хочет восстановить любую перестановку $$$a$$$ такую, что вызов функции sort от неё даст ту же строку $$$s$$$. Помогите ему!

Input format:
Ввод содержит непустую строку $$$s$$$, состоящую из символов 0 и 1.

В этой версии задачи для любого теста существует перестановка длины $$$16$$$, удовлетворяющая условию. Тем не менее, ваш ответ может иметь любую длину, в том числе отличную от $$$16$$$.

Output format:
В первой строке выведите целое число $$$n$$$ — длину перестановки.

Во второй строке выведите $$$n$$$ различных целых чисел $$$a_0, a_1, \ldots, a_{n-1}$$$ ($$$1 \le a_i \le n$$$) — элементы перестановки.

Если существует несколько вариантов ответа, выведите любой из них.

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

Example input:
00000000000000000000000000000000

Example output:
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Example input:
11111111111111111111111111111111

Example output:
16
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

Editorial:
Сортировка слиянием
Contest: VK Cup 2021 - Квалификация (Engine)
Tags: *special, *special, brute force

Рассмотрим следующий код сортировки слиянием на языке Python:

Как можно заметить, этот код использует логирование — важнейший инструмент разработки.

Старший разработчик ВКонтакте Вася сгенерировал перестановку $$$a$$$ (массив из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$), дал её на вход функции sort и получил на выходе строку $$$s$$$. На следующий день строку $$$s$$$ Вася нашёл, а перестановка $$$a$$$ потерялась.

Вася хочет восстановить любую перестановку $$$a$$$ такую, что вызов функции sort от неё даст ту же строку $$$s$$$. Помогите ему!

Input format:
Ввод содержит непустую строку $$$s$$$, состоящую из символов 0 и 1.

В этой версии задачи для любого теста существует перестановка длины не более $$$10^3$$$, удовлетворяющая условию. Тем не менее, ваш ответ может иметь любую длину, в том числе превышающую $$$10^3$$$.

Output format:
В первой строке выведите целое число $$$n$$$ — длину перестановки.

Во второй строке выведите $$$n$$$ различных целых чисел $$$a_0, a_1, \ldots, a_{n-1}$$$ ($$$1 \le a_i \le n$$$) — элементы перестановки.

Если существует несколько вариантов ответа, выведите любой из них.

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

Example input:
00000000000000000000000000000000

Example output:
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Example input:
11111111111111111111111111111111

Example output:
16
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

Editorial:
Предположим, что мы знаем длину перестановки $$$n$$$.
Исходно перестановка имела вид $$$a_0, a_1, \ldots, a_{n-1}$$$. Давайте попробуем её отсортировать, используя рекурсивную функцию из условия.
Единственная проблема, с которой мы столкнёмся — мы не знаем значения элементов, поэтому не умеем выполнять сравнение в строке if a[i] < a[j]. Здесь нам и поможет лог сравнений.
Как только нам приходит запрос на сравнение элемента, обратимся к очередному символу лога. Таким образом мы узнаем, какой из элементов a[i] и a[j] на самом деле меньше, и запишем его в b[k].
По итогам сортировки на первом месте окажется элемент со значением $$$1$$$, на втором — со значением $$$2$$$, и так далее. Например, если после сортировки при $$$n = 6$$$ перестановка примет вид $$$a_3, a_5, a_2, a_0, a_1, a_4$$$, значит, исходная перестановка равна $$$4, 5, 3, 1, 6, 2$$$.
Вспомним, что длину перестановки мы не знаем. Давайте её переберём в диапазоне от $$$1$$$ до $$$10^3$$$. Если по итогам сортировки будут использованы не все символы лога, или же нам потребуется взять символ из лога, когда их там уже не останется, значит, такое значение $$$n$$$ нам не подходит. Если же мы использовали ровно столько символов из лога, сколько нам дано, то мы нашли корректный ответ.
Проверка одного значения $$$n$$$ выполняется за $$$O(n \log n)$$$, следовательно, итоговая сложность составит $$$O(n^2 \log n)$$$.
Love Story
Contest: Codeforces Round 871 (Div. 4)
Difficulty rating: 800
Tags: implementation, strings

Timur loves codeforces. That's why he has a string $$$s$$$ having length $$$10$$$ made containing only lowercase Latin letters. Timur wants to know how many indices string $$$s$$$ differs from the string "codeforces".

For example string $$$s =$$$ "coolforsez" differs from "codeforces" in $$$4$$$ indices, shown in bold.

Help Timur by finding the number of indices where string $$$s$$$ differs from "codeforces".

Note that you can't reorder the characters in the string $$$s$$$.

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

Each test case is one line and contains the string $$$s$$$, consisting of exactly $$$10$$$ lowercase Latin characters.

Output format:
For each test case, output a single integer — the number of indices where string $$$s$$$ differs.

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

Example input:
5
coolforsez
cadafurcie
codeforces
paiuforces
forcescode

Example output:
4
5
0
4
9

Editorial:
You need to implement what is written in the statement. You need to compare the given string $$$s$$$ with the string "codeforces" character by character, counting the number of differences. We know that the length of $$$s$$$ is $$$10$$$, so we can simply iterate through both strings and compare each character at the same index.
If the characters are the same, we move on to the next index. If they are different, we count it as a difference and move on to the next index. Once we have compared all $$$10$$$ characters, we output the number of differences.
Blank Space
Contest: Codeforces Round 871 (Div. 4)
Difficulty rating: 800
Tags: implementation

You are given a binary array $$$a$$$ of $$$n$$$ elements, a binary array is an array consisting only of $$$0$$$s and $$$1$$$s.

A blank space is a segment of consecutive elements consisting of only $$$0$$$s.

Your task is to find the length of the longest blank space.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the length of the array.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_i$$$ ($$$0 \leq a_i \leq 1$$$) — the elements of the array.

Output format:
For each test case, output a single integer — the length of the longest blank space.

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

Example input:
5
5
1 0 0 1 0
4
0 1 1 1
1
0
3
1 1 1
9
1 0 0 0 1 0 0 0 1

Example output:
2
1
1
0
3

Editorial:
We can iterate through the array $$$a$$$ and keep track of the length of the current blank space. Whenever we encounter a $$$0$$$, we increase the length of the current blank space, and whenever we encounter a $$$1$$$, we check if the current blank space is longer than the previous longest blank space. If it is, we update the length of the longest blank space. Finally, we return the length of the longest blank space.
The time complexity of this algorithm is $$$\mathcal{O}(n)$$$.
Mr. Perfectly Fine
Contest: Codeforces Round 871 (Div. 4)
Difficulty rating: 800
Tags: bitmasks, greedy, implementation

Victor wants to become "Mr. Perfectly Fine". For that, he needs to acquire a certain set of skills. More precisely, he has $$$2$$$ skills he needs to acquire.

Victor has $$$n$$$ books. Reading book $$$i$$$ takes him $$$m_i$$$ minutes and will give him some (possibly none) of the required two skills, represented by a binary string of length $$$2$$$.

What is the minimum amount of time required so that Victor acquires all of the two skills?

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of books available.

Then $$$n$$$ lines follow. Line $$$i$$$ contains a positive integer $$$m_i$$$ ($$$1 \leq m_i \leq 2 \cdot 10^5$$$) and a binary string of length $$$2$$$, where $$$s_{i1} = 1$$$ if reading book $$$i$$$ acquires Victor skill $$$1$$$, and $$$s_{i1} = 0$$$ otherwise, and $$$s_{i2} = 1$$$ if reading book $$$i$$$ acquires Victor skill $$$2$$$, and $$$s_{i2} = 0$$$ otherwise.

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

Output format:
For each test case, output a single integer denoting the minimum amount of minutes required for Victor to obtain both needed skills and $$$-1$$$ in case it's impossible to obtain the two skills after reading any amount of books.

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

Note:
In the first test case, we can use books $$$2$$$ and $$$3$$$, with a total amount of minutes spent equal to $$$3 + 4 = 7$$$.

In the second test case, we can use the books $$$1$$$ and $$$4$$$, with a total amount of minutes spent equal to $$$3 + 2 = 5$$$.

In the third test case, we have only one option and that is reading book $$$1$$$ for a total amount of minutes spent equal to $$$5$$$.

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

Example output:
7
5
5
9
-1
8

Editorial:
You can classify the books into four types "00", "01", "10", "11". We will take a book of any type at most once and wont take a book that learns a single skill if that skill is already learned, so there are only two cases to look at
• We take the shortest "01" and the the shortest "10".
• We take the shortest "11".
Out of these options, output the shortest one.
Gold Rush
Contest: Codeforces Round 871 (Div. 4)
Difficulty rating: 1000
Tags: brute force, dfs and similar, dp, implementation

Initially you have a single pile with $$$n$$$ gold nuggets. In an operation you can do the following:

- Take any pile and split it into two piles, so that one of the resulting piles has exactly twice as many gold nuggets as the other. (All piles should have an integer number of nuggets.)

One possible move is to take a pile of size $$$6$$$ and split it into piles of sizes $$$2$$$ and $$$4$$$, which is valid since $$$4$$$ is twice as large as $$$2$$$.

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

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^7$$$) — the starting and target pile sizes, respectively.

Output format:
For each test case, output "YES" if you can make a pile of size exactly $$$m$$$, and "NO" otherwise.

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

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

Note:
The first test case is pictured in the statement. We can make a pile of size $$$4$$$.

In the second test case, we can perform the following operations: $$$\{\color{red}{9}\} \to \{\color{red}{6},3\} \to \{4,2,3\}$$$. The pile that is split apart is colored red before each operation.

In the third test case, we can't perform a single operation.

In the fourth test case, we can't end up with a larger pile than we started with.

Example input:
11
6 4
9 4
4 2
18 27
27 4
27 2
27 10
1 1
3 1
5 1
746001 2984004

Example output:
YES
YES
NO
NO
YES
YES
NO
YES
YES
NO
NO

Editorial:
We can solve this problem recursively. Let the current pile have $$$n$$$ gold nuggets.
• If $$$n=m$$$, then we can make a pile with exactly $$$m$$$ gold nuggets by not doing any operations.
• If $$$n$$$ is not a multiple of $$$3$$$, then it is not possible to make a move, because after a move we split $$$n$$$ into $$$x$$$ and $$$2x$$$, so $$$n=x+2x=3x$$$ for some integer $$$x$$$, meaning $$$n$$$ has to be a multiple of $$$3$$$.
• Finally, if $$$n$$$ is a multiple of $$$3$$$, then we can split the pile into two piles with $$$\frac{n}{3}$$$ and $$$\frac{2n}{3}$$$ gold nuggets, and we can recursively check if we can make a pile with exactly $$$m$$$ gold nuggets.
By the Master Theorem, the time complexity is $$$\mathcal{O}(n^{\log_32}) \approx \mathcal{O}(n^{0.631})$$$. Most compilers and languages optimize the recursion enough for this to pass comfortably. (The model solution in C++ runs in 15 milliseconds.)
The Lakes
Contest: Codeforces Round 871 (Div. 4)
Difficulty rating: 1100
Tags: dfs and similar, dsu, graphs, implementation

You are given an $$$n \times m$$$ grid $$$a$$$ of non-negative integers. The value $$$a_{i,j}$$$ represents the depth of water at the $$$i$$$-th row and $$$j$$$-th column.

A lake is a set of cells such that:

- each cell in the set has $$$a_{i,j} > 0$$$, and
- there exists a path between any pair of cells in the lake by going up, down, left, or right a number of times and without stepping on a cell with $$$a_{i,j} = 0$$$.

The volume of a lake is the sum of depths of all the cells in the lake.

Find the largest volume of a lake in the grid.

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

The first line of each test case contains two integers $$$n, m$$$ ($$$1 \leq n, m \leq 1000$$$) — the number of rows and columns of the grid, respectively.

Then $$$n$$$ lines follow each with $$$m$$$ integers $$$a_{i,j}$$$ ($$$0 \leq a_{i,j} \leq 1000$$$) — the depth of the water at each cell.

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

Output format:
For each test case, output a single integer — the largest volume of a lake in the grid.

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

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

Example output:
10
0
7
16
21

Editorial:
We can approach this problem using Depth First Search (DFS) or Breadth First Search (BFS) on the given grid.
The idea is to consider each cell of the grid as a potential starting point for a lake, and explore all the cells reachable from it by only moving up, down, left or right, without stepping on any cell with depth $$$0$$$. If we reach a dead end, or a cell with depth $$$0$$$, we backtrack and try another direction.
During this exploration, we keep track of the sum of depths of all the cells that we have visited. This sum gives us the volume of the current lake. When we have explored all the reachable cells from a starting point, we compare the volume of this lake with the maximum volume found so far, and update the maximum if necessary.
To implement this approach, we can use a nested loop to iterate through all the cells of the grid. For each cell, we check if its depth is greater than $$$0$$$, and if it has not already been visited in a previous lake. If these conditions are satisfied, we start a DFS/BFS from this cell, and update the maximum volume found so far. See the implementation for more details.
The time complexity is $$$\mathcal{O}(mn)$$$.
Forever Winter
Contest: Codeforces Round 871 (Div. 4)
Difficulty rating: 1300
Tags: dfs and similar, graphs, math

A snowflake graph is generated from two integers $$$x$$$ and $$$y$$$, both greater than $$$1$$$, as follows:

- Start with one central vertex.
- Connect $$$x$$$ new vertices to this central vertex.
- Connect $$$y$$$ new vertices to each of these $$$x$$$ vertices.

The snowflake graph above has a central vertex $$$15$$$, then $$$x=5$$$ vertices attached to it ($$$3$$$, $$$6$$$, $$$7$$$, $$$8$$$, and $$$20$$$), and then $$$y=3$$$ vertices attached to each of those.

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 200$$$; $$$1 \leq m \leq \min\left(1000, \frac{n(n-1)}{2}\right)$$$) — the number of vertices and edges in the graph, respectively.

The next $$$m$$$ lines each contain two integers each $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$) — the numbers of vertices connected by an edge. The graph does not contain multiple edges and self-loops.

It is guaranteed that this graph is a snowflake graph for some integers $$$x$$$ and $$$y$$$ both greater than $$$1$$$.

Output format:
For each test case, on a separate line output the values of $$$x$$$ and $$$y$$$, in that order, separated by a space.

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

Note:
The first test case is pictured in the statement. Note that the output 3 5 is incorrect, since $$$x$$$ should be output before $$$y$$$.

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

Example output:
5 3
2 2
2 3

Editorial:
The degree of a vertex is the number of vertices connected to it. We can count the degree of a vertex by seeing how many times it appears in the input.
Let's count the degrees of the vertices in a snowflake graph.
• The starting vertex has degree $$$x$$$.
• Each of the $$$x$$$ newly-generated vertices has degree $$$y+1$$$ (they have $$$y$$$ new neighbors, along with the starting vertex).
• Each of the $$$x \times y$$$ newly-generated vertices has degree $$$1$$$ (they are only connected to the previous vertex).
However, there is an edge case. If $$$x=y+1$$$, then the first two rows combine:
The time complexity is $$$\mathcal{O}(n+m)$$$ per test case.