{"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":"CFK"},"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":"[{\"iden\":\"statement\",\"content\":\"Monocarp 玩一款名为《Moonbound》的电脑游戏。这个游戏的主要目标是使用物质操纵器——一个非常强大的神器——拯救银河系免受外星势力的入侵。不过，当 Monocarp 不忙于拯救银河系时——事实上，他现在只是在为自己的角色建造一座房子。\\n\\n现在 Monocarp 需要为房子建造一堵墙。Moonbound 世界的整个结构由方块组成，Monocarp 想要建造的墙也不例外。这堵墙将呈正方形，由 $n$ 行水平排列的方块组成，每行包含 $n$ 个方块（$n$ 为偶数）。我们将第 $i$ 行第 $j$ 列方块的位置记为 ($i$, $j$)。\\n\\nMonocarp 希望用两种类型的方块建造这堵墙：石砖和沙砖。Monocarp 认为，当不同类型的方块以棋盘样式排列时，墙会显得美观：左上角的方块应为石砖，其右侧的方块应为沙砖，再右侧的方块应为石砖，依此类推；第二行的第一个方块应为沙砖，第二个方块应为石砖，依此类推。形式化地说，若 $i + j$ 能被 $2$ 整除，则位置 ($i$, $j$) 应放置石砖；否则应放置沙砖。\\n\\n物质操纵器有两种放置方块的模式，但两种模式都对放置方块的位置有特殊要求。我们称一个不包含任何方块的位置 ($i$, $j$) 为 _空闲_，当且仅当它位于边界上（$i = 1$、$i = n$、$j = 1$ 或 $j = n$），或与至少一个已包含方块的位置相邻（共享一条边）。\\n\\n方块可以通过两种模式放置：要么选择任意一个 _空闲_ 位置，并在其中放置一个选定类型的方块；要么选择一个 $2 \\\\times 2$ 的正方形区域，该区域至少包含一个 _空闲_ 位置，并将该正方形内所有 _空闲_ 位置都填充为 _相同_ 类型的选定方块。\\n\\nMonocarp 希望使用物质操纵器在不超过 $\\\\frac{3n^2}{4}$ 次操作内完成墙体建造。如果他在本应放置其他类型方块的位置放置了错误类型的方块，他将不得不拆除墙体的一部分，这将耗费大量时间——因此 Monocarp 不会执行任何在错误位置放置方块的操作。请帮他制定一个操作计划！\\n\\n输入仅包含一个 _偶数_ 整数 $n$（$2 \\\\leq n \\\\leq 50$）——墙的行数（也是每行的方块数）。\"},{\"iden\":\"input\",\"content\":\"输入仅包含一个 _偶数_ 整数 $n$（$2 \\\\leq n \\\\leq 50$）——墙的行数（也是每行的方块数）。\"},{\"iden\":\"output\",\"content\":\"第一行输出 $k$（$1 \\\\leq k \\\\leq \\\\frac{3n^2}{4}$）——建造墙体所需的物质操纵器操作次数。接下来 $k$ 行，每行描述一个操作，格式为四个整数 $t$ $x$ $y$ $b$：\\n\\n$t$ 表示操作类型：若为 $1$，表示仅填充一个位置；若为 $2$，表示填充一个 $2 \\\\times 2$ 的正方形区域；\\n$x$ $y$ 是 Monocarp 填充的位置坐标。若操作类型为 $1$，则位置 ($x$, $y$) 将被填充——且在操作前该位置必须是 _空闲_ 的；若操作类型为 $2$，则位置 ($x$, $y$)、($x$, $y + 1$)、($x + 1$, $y$) 和 ($x + 1$, $y + 1$) 将被填充——且其中至少有一个位置在操作前是 _空闲_ 的；\\n$b$ 表示所有空闲位置将被填充的方块类型（$1$ 表示石砖，$2$ 表示沙砖）。\\n\\n任何操作都不能导致某个位置出现不属于该位置的方块。当填充 $2 \\\\times 2$ 正方形时，该正方形内不能有任何位置超出墙体边界（因此若 $t = 2$，则 $1 \\\\leq x, y \\\\leq n - 1$）。\\n\\n若存在多个满足 $k \\\\leq \\\\frac{3n^2}{4}$ 的可行方案，请输出其中任意一个。注意，不同类型的方块必须按棋盘样式排列，且位置 ($1$, $1$) 必须为石砖。\"},{\"iden\":\"note\",\"content\":\"第一个示例中的操作序列（白色代表空位置，深灰代表石砖，浅灰代表沙砖）： \"}]}","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be even, $ 2 \\leq n \\leq 50 $.  \nThe wall is an $ n \\times n $ grid.  \nFor position $ (i, j) $, the target block type is:  \n- Stone if $ i + j \\equiv 0 \\pmod{2} $,  \n- Sand if $ i + j \\equiv 1 \\pmod{2} $.  \n\n**Constraints**  \n- Initial grid: all positions empty.  \n- Two allowed operations:  \n  1. **Type 1**: Place a single block of correct type on a *free* position.  \n     - A position is *free* if it is on the border ($ i=1 $, $ i=n $, $ j=1 $, or $ j=n $) or adjacent (sharing a side) to an already filled position.  \n  2. **Type 2**: Fill all empty positions in a $ 2 \\times 2 $ square with the *same* correct block type, provided at least one position in the square is *free*.  \n     - The square must lie entirely within the grid: $ 1 \\leq x \\leq n-1 $, $ 1 \\leq y \\leq n-1 $.  \n- No block may be placed in a position where the type does not match the chequered pattern.  \n- Total operations $ k \\leq \\frac{3n^2}{4} $.  \n\n**Objective**  \nConstruct a sequence of $ k $ operations (each of Type 1 or Type 2) that fills the entire grid with the correct chequered pattern, starting from all empty positions, under the above constraints.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFK","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}