Busy Beaver has discovered that someone has mixed up his toy marbles!
There are $$$N$$$ containers, numbered from $$$1$$$ to $$$N$$$. The $$$i$$$-th container currently contains a single marble of color $$$c_i$$$.
Busy Beaver wants to tidy up his marbles so that the $$$i$$$-th container only contains marbles of color $$$i$$$. To achieve this, he can perform either of the following actions any number of times (possibly zero):
Find a way to organize the marbles using the minimum number of actions.
The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$) — the number of containers.
The second line contains $$$N$$$ integers $$$c_1, c_2, \dots, c_N$$$ ($$$1 \leq c_i \leq N$$$) — the marble initially in each container.
On the first line, print a single integer $$$K$$$ — the minimum number of actions required.
On the next $$$K$$$ lines, describe the actions in order, one per line. Each action should be in one of the following formats:
If there are multiple ways to achieve the goal in the minimum number of actions, you may print any valid solution.
There are two subtasks for this problem.
42 4 3 1
2 1 2 4 1 1 2
83 6 7 6 3 6 8 3
6 2 6 4 2 6 2 1 8 7 1 7 3 2 3 1 2 3 5
In the first test case, it is able to achieve the goal in two actions:
It is impossible to achieve the goal in less than two actions.
On a rectangular grid, a snake of size $$$k$$$ is defined to be a subset of cells that is formed by taking the first $$$k$$$ numbered cells in the following figure, where cells are numbered along a path with alternating right and down steps:
Additionally, subsets that are rotations, translations, or reflections of these shapes are also considered snakes. A grid is considered good if every connected component consisting of equal values in the grid is a snake.
Busy Beaver has an $$$N \times M$$$ grid with rows numbered $$$0, \dots, N-1$$$ and columns numbered $$$0, \dots, M-1$$$, where each cell $$$(i, j)$$$ in row $$$i$$$, column $$$j$$$ has a value $$$a_{ij}$$$. Since he's afraid of snakes, he wants you to answer $$$Q$$$ of the following queries: given a contiguous subrectangle of the grid, determine whether or not the subgrid is good.
The first line contains 2 integers, $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 1000$$$) — the dimensions of the grid.
Each of the next $$$N$$$ rows contains $$$M$$$ integers, with the $$$j$$$-th element of the $$$i$$$-th row being $$$a_{i,j}$$$ ($$$1 \leq a_{i, j} \leq 10^6$$$) — the number written in the $$$j$$$-th cell of the $$$i$$$-th row.
The next line contains a single integer, $$$Q$$$ ($$$1 \leq Q \leq 5 \cdot 10^5$$$) — the number of queries.
The next $$$Q$$$ lines describe the queries, Each line contains 4 integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ $$$(0 \leq x_1 \leq x_2 \lt N,$$$ $$$ 0 \leq y_1 \leq y_2 \lt M)$$$, representing a query asking whether the rectangular subgrid with top left corner at $$$(x_1, y_1)$$$ and bottom right corner at $$$(x_2, y_2)$$$ is good.
For each query, output "YES" (without quotes) if the corresponding subgrid consists only of snakes, and "NO" (without quotes) otherwise.
You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).
There are four subtasks for this problem.
10 9 1 1 2 2 3 3 2 2 1 4 1 1 3 3 2 2 4 4 4 4 1 1 2 2 3 4 4 4 2 2 1 1 3 3 4 4 2 2 3 4 4 2 2 3 3 1 1 3 3 4 4 2 2 3 2 1 1 3 3 4 4 2 4 2 2 1 2 4 4 3 3 4 1 3 3 4 4 2 2 3 4 3 3 1 1 1 1 4 4 4 5 0 1 6 5 5 4 7 8 0 6 2 8 6 0 9 3 8 5 9 8
YES NO NO YES NO
If we color the sample grid with respect to the value in each cell, we get
Busy Beaver is visiting MIT, so he decided to have a tour around campus.
The campus consists of $$$N$$$ rooms and $$$N-1$$$ corridors between them. The rooms are enumerated consecutively from $$$1$$$ to $$$N$$$, and the $$$i$$$-th corridor has a known length $$$w_i$$$ and can be traversed in both directions. The layout of campus is also such that between any two rooms, there is exactly one way to go from one to another through these corridors without going through any room twice. Define the level of a room to be the minimum number of corridors needed to get from the Great Dome (room $$$1$$$) to this room. For instance, the Great Dome is level $$$0$$$, and any room directly connected to it would be level $$$1$$$. Let $$$k$$$ be the highest level of any room on campus, and denote $$$d(u, v)$$$ to be the length of the shortest path between rooms $$$u, v$$$.
Busy Beaver wants his tour to be interesting. Starting from the Great Dome (room $$$1$$$), he wishes to visit a sequence of rooms $$$a_1, \dots, a_k$$$ such that for each $$$1 \leq i \leq k$$$, room $$$a_i$$$ is on level $$$i$$$, and for each $$$1 \leq i \lt k$$$, rooms $$$a_i, a_{i+1}$$$ are not connected by a corridor. As Busy Beaver is busy as usual, he also wants to minimize the total distance of the tour, which is $$$$$$d(1, a_1) + d(a_1, a_2) + \dots + d(a_{k-1}, a_k).$$$$$$
Since the MIT campus is very complex, Busy Beaver needs your help to plan out his tour. Help him find out the minimum length of an interesting tour.
The first line consists of a single integer $$$N$$$ ($$$2 \le N \le 2 \cdot 10^5$$$) — the number of rooms at the MIT campus.
Each of the next $$$N-1$$$ lines contains three integers $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \le u,v \le N$$$, $$$u \neq v$$$, $$$1 \le w \le 10^7$$$) — a corridor between rooms $$$u$$$ and $$$v$$$ with the length $$$w$$$.
It is guaranteed that there is exactly one simple path between any two rooms, and that at least one interesting tour exists.
Output a single integer, the minimal distance of an interesting MIT tour.
There are three subtasks for this problem.
31 2 11 3 1
1
51 2 31 3 13 4 23 5 3
9
In the first test case, there are two possible interesting tours:
In the second test case, notice that both rooms of level $$$2$$$ are connected to room $$$3$$$. Therefore, no interesting tour can have $$$a_1 = 3$$$, or otherwise it will violate the condition that $$$a_1, a_2$$$ are not connected by a corridor. Therefore, there are two possible interesting tours:
This is an "output-only" problem. The test cases are made available to you. However, due to the large output size, you should still submit a program that reads the input and produces the outputs within the time limit.
Busy Beaver generated a random undirected graph with $$$N$$$ vertices and $$$M$$$ edges, where $$$M$$$ is a multiple of $$$3$$$. Now, he wants to partition the edges into $$$M/3$$$ paths of length $$$3$$$ (possibly starting and ending at the same vertex). Can you help Busy Beaver find such a partition?
Please download the test data using this link.
The first line of input contains two integers $$$N$$$ and $$$M$$$ — the number of vertices and edges in the graph, respectively.
The $$$i$$$th of the next $$$M$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le N, u_i \ne v_i$$$) — the endpoints of the $$$i$$$th edge.
It is guaranteed that the $$$M$$$ edges were generated randomly. Formally, out of the $$$\frac{N(N-1)}{2}$$$ possible edges, $$$M$$$ distinct edges were chosen uniformly at random without replacement.
Output $$$M/3$$$ lines. The $$$i$$$th line should contain $$$4$$$ integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, and $$$d_i$$$ ($$$1 \le a_i,b_i,c_i,d_i \le N$$$), representing a path using edges $$$(a_i,b_i)$$$, $$$(b_i,c_i)$$$, and $$$(c_i,d_i)$$$.
It is allowed to have $$$a_i = d_i$$$. Your output should satisfy $$$$$$ \bigcup_{i=1}^{M/3} \{\{a_i,b_i\},\{b_i,c_i\},\{c_i,d_i\}\} = \bigcup_{i=1}^M \{\{u_i,v_i\}\}. $$$$$$
There are $$$10$$$ test cases in total, each worth $$$10$$$ points. For your convenience, the values of $$$N$$$ and $$$M$$$ in each test case are shown in the following list:
It is guaranteed that each of the $$$10$$$ generated graphs has a valid partition.
10 153 1010 43 65 810 95 21 41 91 78 31 66 1010 28 24 3
2 5 8 2 8 3 10 2 3 4 1 7 6 1 9 10 3 6 10 4
The sample is provided to illustrate the input and output format. It is not scored.
The sample graph and partition are shown in the figure below. Note that the path $$$2 - 5 - 8 - 2$$$ starts and ends at the same vertex, which is allowed.
Busy Beaver is playing with his favorite blocks. There are $$$N$$$ blocks arranged in a row, each block having a color $$$c_i$$$. Busy Beaver hates seeing blocks of the same color next to each other, so he would like to rearrange the blocks into multiple rows, such that the blocks in each row are in the same ordering as they were in the original line, and no line has two consecutive blocks of the same color. Each of the $$$N$$$ original blocks should belong to exactly one of these rows.
Please help Busy Beaver determine an arrangement of blocks that uses the least possible number of lines.
Each test contains multiple test cases. The first line of input contains a single integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$, the number of test cases. The description of each test case follows.
The first line of each test case contains a single positive integer $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$) — the number of blocks.
The second line contains $$$N$$$ space separated integers $$$c_i$$$ ($$$1 \leq c_i \leq 10^9$$$) — the color of the $$$i$$$th block.
It is guaranteed that the sum of $$$N$$$ across all test cases is no more than $$$2 \cdot 10^5$$$.
For each test case, the first line of output should contain a single positive integer $$$k$$$, the minimum number of rows that Busy Beaver needs to rearrange the blocks to satisfy his conditions.
For each of the next $$$k$$$ lines, output the number of blocks in that row, as well as the indices of the blocks themselves, space separated. Each of the rows must be nonempty.
If there are multiple solutions with the same minimum number of rows needed, output any one of them.
You will receive $$$30\%$$$ of the points for each subtask if your value of $$$k$$$ is correct, but the construction is incorrect. To receive this partial credit, you still need to output $$$k$$$ lines for each test describing some rearrangement of the blocks into $$$k$$$ nonempty rows.
For instance, the following output would receive partial credit on the sample input:
2
1 1
1 2
1
3 1 2 3
2
3 1 2 3
1 4
while the following does not:
2
2 1 2
0
1
0
2
1 1
1 2
There are two subtasks for this problem.
322 231 2 141 1 2 1
2 1 1 1 2 1 3 1 2 3 2 1 1 3 2 3 4
In the first test case, it is optimal to create two rows, each with one of the two blocks. It is impossible to use only one row, since the two blocks have the same color.
In the second test case, we can use one row to contain all three blocks.
In the third test case, it is optimal to create two rows, with one containing the first block and the second containing the remaining three blocks.