Let $$$T = (V, E)$$$ be a tree with $$$n$$$ vertices and $$$n-1$$$ edges. Each edge of the tree can be assigned a colour from $$$\{0, 1, \dots, K-1\}$$$.

A simple path in a tree is called a $$$K$$$-rainbow path if all edges along the path of length $$$K$$$ have distinct colours. An edge is said to be $$$K$$$-rainbow-valid if it lies on at least one $$$K$$$-rainbow path. A tree is called a $$$K$$$-tree if every edge in the tree is $$$K$$$-rainbow-valid.

Your task is to assign colours to the edges of a given tree to form a K-tree with the largest possible $$$K$$$. For each edge $$$e$$$, you must report its assigned colour $$$c(e) \in \{0, 1, \dots, K-1\}$$$ and the endpoints of a K-rainbow path that contains $$$e$$$.

All indices are zero-based. If multiple valid colourings or paths exist, any may be output.

Every morning at 9 AM sharp, your manager posts a Slack message: "Good morning team! We're restructuring again to align with our strategic vision!!"

Here at MegaCorp Inc, we don't have departments; we have $$$m$$$ dynamic Synergy Hubs numbered $$$1$$$ to $$$m$$$. You are starting your journey today in Hub $$$1$$$, which, as you recall, brought down production twice in the last month.

To navigate this fluid ecosystem, we transition using one of our $$$k$$$ Key Strategic Methodologies (e.g., Agile Transformation, Lean Optimisation, Synergistic Disruption). In other words, there are several forms you can file to exit/enter hubs, which can be categorized into $$$k$$$ methodologies. Who comes up with this stuff?

Management maintains meticulous transparency. Each Hub $$$i \in \{1, \dots, m\}$$$ has its own unique set of forms for each Methodology $$$j \in \{1, \dots, k\}$$$, which for some Hub $$$i$$$ can be split as follows.

There are $$$c_{i,j}$$$ unique Departure Forms of type $$$j$$$ (like Agile Exit Protocol A-1).

Similarly, there are $$$c_{i,j}$$$ unique Onboarding Forms of type $$$j$$$ for that Hub.

Management assures us that the number of ways to leave a Hub using a methodology is always the same as the number of ways to join it using that same methodology. It's about Process Symmetry.

Every day, you must execute a "Strategic Realignment." This consists of two steps:

• LEAVE your current Hub. You must file one of its available Departure Forms.
• JOIN a new Hub. You must file one of the Onboarding Forms for the Hub you are moving to. (Note: You are allowed to "re-org" right back into the same Hub. This is called "Re-committing to your Core Mission.")

The Methodology type you use to leave a Hub CANNOT be the same as the Methodology type you use to join your new Hub.

As your manager explained: "If you exit with Synergy, you must enter with Lean. We can't have you leaving and joining via Agile! Think of the paradigm shifts!"

Your Task

Your manager, holding his morning coffee, now turns to you. "For our Future-State Planning meeting, I need a simple number."

How many distinct sequences of forms could you possibly file over exactly $$$d$$$ days?

You look at the clock. It's 9:05 AM. It's going to be a long week.

Long ago, in a quiet tower filled with bubbling cauldrons and dusty spellbooks, there lived a rather absent-minded magician. One evening, he decided to brew a Potion of Power. The potion starts with a magical potency of $$$1$$$ — modest, but full of potential.

The magician owns two ancient runes, called Rune $$$A$$$ and Rune $$$B$$$, each capable of multiplying the potion's current magical power by a fixed (nonnegative) integral factor. He does, however, have a terrible memory. He can't recall the exact values of these multipliers — only that:

• The multiplier of Rune $$$B$$$ is exactly one greater than that of Rune $$$A$$$.
• If he ever applies Rune $$$A$$$ immediately after Rune $$$B$$$, the potion reacts violently and loses all of its power (drops to zero).

Despite this risk, the magician is quite fond of experimenting. He decides to apply every possible sequence of $$$n$$$ runes, each either $$$A$$$ or $$$B$$$, to the initial potion to see what kinds of magical strengths he can obtain.

As he is tinkering with the runes, he realizes that he will have way too much potion. He is only planning to take a single sip — exactly one unit of magical power! Now he will need to store the remaining power from all experiments in his flasks.

By some strange coincidence of fate, as often happens in magic, each of his (infinitely many) flasks can hold exactly $$$n + 1$$$ units of magical power.

The magician is an orderly man; he refuses to leave any flask partially filled. So now he wonders:

Will it be possible to divide all of the leftover magical power (after taking his sip) into flasks such that no flask is partially filled, regardless of what the power multiplier of rune $$$A$$$ is?

Nicolas is creating a new playlist with songs from different genres. He has $$$n$$$ different genres, and each genre has $$$c_i$$$ different songs. Each song is in exactly one genre. He wants to add $$$m$$$ songs to the playlist, and they should be chosen from the different genres as evenly as possible so the playlist has a smooth sound.

Formally, given $$$n$$$ genres with $$$c_i$$$ songs each, he wants to choose $$$m$$$ songs without replacement as evenly as possible. What's the minimum difference between the number of songs from the most taken genre and the number of songs from the least taken genre?

Assuming $$$k_i$$$ is the amount of songs he picks from genre $$$i$$$, he wants to minimize:

$$$$$$\max k_i - \min k_i$$$$$$

subject to $$$0 \leq k_i \leq c_i$$$ and $$$\sum k_i = m$$$.

A small kingdom consists of one road. Every house on the street is numbered sequentially from $$$A$$$ to $$$B$$$ $$$(A, A + 1, \dots, B - 1, B)$$$. The key number of a house is the largest odd divisor of the house number.

The king is throwing a party and wants to invite a select number of VIP guests. Only guests living in houses with a key number of $$$1$$$ are allowed to attend the party.

To estimate how much food and how many drinks he needs to buy, the king wants to know how many VIP guests there are.

You have a grid of $$$N \times M$$$ square cells, with height $$$N$$$ units and width $$$M$$$ units. The outer border of the grid is a wall. There are 2 holes in the wall: to access the entrance (top left) cell and the exit (bottom right) cell.

The internal part of the grid consists of $$$L=2\cdot N \cdot M-(N+M)$$$ internal segments of unit length. You have $$$K$$$ walls of unit length, and you must place each of those walls at one of the internal segments (you can't place two or more walls at the same segment).

For example, the picture below shows a grid with $$$N=3$$$ and $$$M=5$$$. There are $$$L=22$$$ internal segments and there are $$$K=6$$$ walls placed.

You place walls randomly. That is, you take a wall, pick one of the free internal segments with equal probability, and place the wall there. You repeat this procedure until you have placed all $$$K$$$ walls. Let's call the result a random maze with $$$K$$$ walls.

After this, you check if the maze is solvable. The maze is solvable if there is a path from the top left cell to the bottom right cell. Formally, the maze is solvable if there exists a sequence of cells, such that the first cell in the sequence is the top left cell, the last cell in the sequence is the bottom right cell, and for every two cells adjacent in the sequence, they are adjacent by side in the grid, and there is no wall placed between them.

For every integer $$$K \in [0, L]$$$, compute the probability that a random maze with $$$K$$$ walls is solvable.

Define $$$d(a,b)$$$ — distance between two strings $$$a$$$ and $$$b$$$ as the number of single-character insertions and deletions needed to transform one string to another.

You are given a list of $$$n$$$ pairwise distinct strings $$$s_1, \dots, s_n$$$ consisting of only lowercase Latin letters. For every string, find the nearest string to it from the same list. That is, for every $$$i$$$, find such $$$j$$$ that $$$j \ne i$$$ and $$$d(s_i, s_j)$$$ is the smallest possible. If there are multiple strings with the same distance, pick the lexicographically smallest one.

You have a transparent band of length N units and width M units. It's split into $$$N \times M$$$ unit squares.

You take two sides of the band (the ones with length M units), rotate one of them by 180 degrees, and connect them, getting a Möbius band of length N and width M. Then you paint each square on the band in one of $$$K$$$ colors.

Two painted Möbius bands of the same size are considered to have the same coloring if you can move one of them in such a way that it becomes indistinguishable from the other one. Otherwise, they have different colorings.

Find the number of colorings of the given Möbius band in K colors, modulo $$$10^9+7$$$.

In Mancala solitaire, you are given stones in a line of holes, with hole 0 being special and containing no stones to start with.

In each turn, you choose a number $$$k$$$ such that there are exactly $$$k$$$ stones in hole $$$k$$$. Then you remove the stones from hole $$$k$$$ and put one stone each into the holes $$$k - 1, k - 2, \dots, 1, 0$$$:

The goal is to get all stones in hole 0 after some number of turns. (For example, you can do this in the above example by picking $$$k_1=3, k_2=1, k_3=2$$$, and finally $$$k_4=1$$$.)

You want to show this game to your friend and create a starting position that makes it possible for him to successfully complete the game (getting all stones in hole 0). Give such a starting position for $$$N$$$ stones. It is guaranteed that this is always possible.

You are given a tree $$$T$$$, and an undirected simple graph $$$G$$$. Both $$$T$$$ and $$$G$$$ have vertices numbered $$$1, 2, \dots, N$$$.

A pair of vertices $$$(u, v)$$$ is called good if the unique path between $$$u$$$ and $$$v$$$ in the tree $$$T$$$ is also a path in $$$G$$$.

Count the number of ordered good pairs $$$(u, v)$$$.

Note that $$$(u, u)$$$ is considered good for all $$$u$$$ (the path of length $$$0$$$).

You are an intern at a hyperscale AI data center that manages a linear array of $$$n$$$ GPUs. The $$$i$$$-th GPU currently runs a compute load of $$$a_i$$$.

The data center hosts workloads for $$$m$$$ different companies. Each company $$$j$$$ uses a contiguous range of GPUs from index $$$L_j$$$ to $$$R_j$$$. Different companies may share some GPUs if their computations are colocated for efficiency, so these ranges can overlap.

Before a major demonstration, the management team sets strict balance requirements. For each company $$$j$$$, the total effective compute load across its range must lie between $$$A_j$$$ and $$$B_j$$$ inclusive.

You are allowed to adjust the load of each GPU by applying an integer change $$$\Delta_i$$$. Each adjustment can either increase or decrease the load, but all must stay within a non-negative common safety limit $$$k$$$, meaning every GPU's load can change by at most $$$k$$$ units. The smaller the limit, the better the system stability, so you aim to meet all company requirements using the smallest possible $$$k$$$.

Additionally, for hardware stability, each GPU must remain above the minimal safe operating load after adjustment: $$$a_i + \Delta_i \ge 1$$$ for all $$$i$$$.

Find the minimum integer $$$k$$$ such that there exist integer adjustments $$$\Delta_1, \Delta_2, \ldots, \Delta_n$$$ satisfying, for every company $$$j$$$,

$$$$$$ A_j \le (a_{L_j} + \Delta_{L_j}) + (a_{L_j+1} + \Delta_{L_j+1}) + \dots + (a_{R_j} + \Delta_{R_j}) \le B_j. $$$$$$

If this is impossible for any $$$k$$$, output -1.