{"problem":{"name":"K. Boomerangs","description":{"content":"Let $G = (V, E)$ be a simple undirected graph with $N$ vertices and $M$ edges, where $V = {1, \\\\dots, N}$. A tuple $angle.l u, v, w angle.r$ is called as boomerang in $G$ if and only if ${(u, v), (v, ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10200K"},"statements":[{"statement_type":"Markdown","content":"Let $G = (V, E)$ be a simple undirected graph with $N$ vertices and $M$ edges, where $V = {1, \\\\dots, N}$. A tuple $angle.l u, v, w angle.r$ is called as boomerang in $G$ if and only if ${(u, v), (v, w)} subset.eq E$ and $u != w$; in other words, a boomerang consists of two edges which share a common vertex.\n\nGiven $G$, your task is to find as many disjoint boomerangs as possible in $G$. A set $S$ contains disjoint boomerangs if and only if each edge in $G$ only appears at most once (in one boomerang) in $S$. You may output any valid disjoint boomerangs, but the number of disjoint boomerangs should be maximum.\n\nFor example, consider a graph $G = (V, E)$ of $N = 5$ vertices and $M = 7$ edges where $E = {(1, 2)$, $(1, 4)$, $(2, 3)$, $(2, 4)$, $(2, 5)$, $(3, 4)$, $(3, 5)}$.\n\nThe maximum number of disjoint boomerangs in this example graph is $3$. One example set containing the $3$ disjoint boomerangs is ${angle.l 4, 1, 2 angle.r, angle.l 4, 3, 2 angle.r, angle.l 2, 5, 3 angle.r}$; no set can contain more than $3$ disjoint boomerangs in this example.\n\nInput begins with a line containing two integers: $N$ $M$ ($1 <= N, M <= 100000$), representing the number of vertices and the number edges in $G$, respectively. The next $M$ lines, each contains two integers: $u_i$ $v_i$ ($1 <= u_i < v_i <= N$), representing the edge $(u_i, v_i)$ in $G$. You may safely assume that each edge appears at most once in the given list.\n\nThe first line of output contains an integer: $K$, representing the maximum number of disjoint boomerangs in $G$. The next $K$ lines, each contains three integers: $u$ $v$ $w$ (each separated by a single space), representing a boomerang $angle.l u, v, w angle.r$. All boomerangs in the output should be disjoint. If there is more than one valid solution, you can output any of them.\n\n## Input\n\nInput begins with a line containing two integers: $N$ $M$ ($1 <= N, M <= 100000$), representing the number of vertices and the number edges in $G$, respectively. The next $M$ lines, each contains two integers: $u_i$ $v_i$ ($1 <= u_i < v_i <= N$), representing the edge $(u_i, v_i)$ in $G$. You may safely assume that each edge appears at most once in the given list.\n\n## Output\n\nThe first line of output contains an integer: $K$, representing the maximum number of disjoint boomerangs in $G$. The next $K$ lines, each contains three integers: $u$ $v$ $w$ (each separated by a single space), representing a boomerang $angle.l u, v, w angle.r$. All boomerangs in the output should be disjoint. If there is more than one valid solution, you can output any of them.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the number of towers.  \n- Let $ H_k = (h_{k,1}, h_{k,2}, \\dots, h_{k,n_k}) $ be a sequence of distinct positive integers representing tower heights.  \n\n**Graph Construction**  \nConstruct an undirected graph $ G_k = (V_k, E_k) $ where:  \n- $ V_k = \\{1, 2, \\dots, n_k\\} $ (towers indexed left to right).  \n- For each tower $ i \\in V_k $:  \n  - Let $ \\text{left}(i) $ be the largest index $ j < i $ such that $ h_{k,j} > h_{k,i} $, if it exists. Add edge $ (i, \\text{left}(i)) $.  \n  - Let $ \\text{right}(i) $ be the smallest index $ j > i $ such that $ h_{k,j} > h_{k,i} $, if it exists. Add edge $ (i, \\text{right}(i)) $.  \n- $ E_k $ is the set of all such edges.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 128 $  \n2. $ 1 \\le n_k \\le 10^6 $ for each test case  \n3. $ \\sum_{k=1}^T n_k \\le 5 \\times 10^6 $  \n4. All $ h_{k,i} $ are distinct.  \n\n**Objective**  \nFind the chromatic number $ \\chi(G_k) $ of $ G_k $, and output a valid $ \\chi(G_k) $-coloring of $ V_k $ such that no edge in $ E_k $ connects two vertices of the same color.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10200K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}