{"problem":{"name":"D. Wizard's Tour","description":{"content":"All Berland residents are waiting for an unprecedented tour of wizard in his Blue Helicopter over the cities of Berland! It is well-known that there are _n_ cities in Berland, some pairs of which are","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF860D"},"statements":[{"statement_type":"Markdown","content":"All Berland residents are waiting for an unprecedented tour of wizard in his Blue Helicopter over the cities of Berland!\n\nIt is well-known that there are _n_ cities in Berland, some pairs of which are connected by bidirectional roads. Each pair of cities is connected by no more than one road. It is not guaranteed that the road network is _connected_, i.e. it is possible that you can't reach some city from some other.\n\nThe tour will contain several episodes. In each of the episodes:\n\n*   the wizard will disembark at some city _x_ from the Helicopter;\n*   he will give a performance and show a movie for free at the city _x_;\n*   he will drive to some neighboring city _y_ using a road;\n*   he will give a performance and show a movie for free at the city _y_;\n*   he will drive to some neighboring to _y_ city _z_;\n*   he will give a performance and show a movie for free at the city _z_;\n*   he will embark the Helicopter and fly away from the city _z_.\n\nIt is known that the wizard doesn't like to use roads, so he agrees to use each road at most once (regardless of direction). In other words, for road between _a_ and _b_ he only can drive once from _a_ to _b_, or drive once from _b_ to _a_, or do not use this road at all.\n\nThe wizards wants to plan as many episodes as possible without violation the above rules. Help the wizard!\n\nPlease note that the wizard can visit the same city multiple times, the restriction is on roads only.\n\n## Input\n\nThe first line contains two integers _n_, _m_ (1 ≤ _n_ ≤ 2·105, 0 ≤ _m_ ≤ 2·105) — the number of cities and the number of roads in Berland, respectively.\n\nThe roads description follow, one in each line. Each description is a pair of two integers _a__i_, _b__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_, _a__i_ ≠ _b__i_), where _a__i_ and _b__i_ are the ids of the cities connected by the _i_\\-th road. It is guaranteed that there are no two roads connecting the same pair of cities. Every road is bidirectional. The cities are numbered from 1 to _n_.\n\nIt is possible that the road network in Berland is not connected.\n\n## Output\n\nIn the first line print _w_ — the maximum possible number of episodes. The next _w_ lines should contain the episodes in format _x_, _y_, _z_ — the three integers denoting the ids of the cities in the order of the wizard's visits.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"所有贝兰居民都在期待巫师乘坐他的蓝色直升机飞越贝兰各城市的前所未有的巡游！\n\n众所周知，贝兰有 #cf_span[n] 座城市，其中一些城市对由双向道路连接。每对城市之间至多有一条道路。道路网络不一定 _连通_，即可能存在某些城市无法从其他城市到达的情况。\n\n巡游将包含若干集。在每一集中：\n\n已知巫师不喜欢使用道路，因此他同意每条道路最多使用一次（无论方向）。换句话说，对于连接 #cf_span[a] 和 #cf_span[b] 的道路，他只能从 #cf_span[a] 到 #cf_span[b] 行驶一次，或从 #cf_span[b] 到 #cf_span[a] 行驶一次，或完全不使用这条道路。\n\n巫师希望在不违反上述规则的前提下，规划尽可能多的集数。请帮助巫师！\n\n请注意，巫师可以多次访问同一座城市，限制仅针对道路。\n\n第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[1 ≤ n ≤ 2·105], #cf_span[0 ≤ m ≤ 2·105]) —— 分别表示贝兰的城市数量和道路数量。\n\n接下来是道路描述，每行一条。每条描述是一对两个整数 #cf_span[ai, bi] (#cf_span[1 ≤ ai, bi ≤ n], #cf_span[ai ≠ bi])，其中 #cf_span[ai] 和 #cf_span[bi] 是由第 #cf_span[i] 条道路连接的两座城市的编号。保证不存在两条道路连接相同的两个城市。每条道路都是双向的。城市编号从 #cf_span[1] 到 #cf_span[n]。\n\n贝兰的道路网络可能不连通。\n\n第一行输出 #cf_span[w] —— 最多可能的集数。接下来的 #cf_span[w] 行应以格式 #cf_span[x], #cf_span[y], #cf_span[z] 输出每集内容，这三个整数表示巫师访问城市的顺序。\n\n## Input\n\n第一行包含两个整数 #cf_span[n], #cf_span[m] (#cf_span[1 ≤ n ≤ 2·105], #cf_span[0 ≤ m ≤ 2·105]) —— 分别表示贝兰的城市数量和道路数量。接下来是道路描述，每行一条。每条描述是一对两个整数 #cf_span[ai, bi] (#cf_span[1 ≤ ai, bi ≤ n], #cf_span[ai ≠ bi])，其中 #cf_span[ai] 和 #cf_span[bi] 是由第 #cf_span[i] 条道路连接的两座城市的编号。保证不存在两条道路连接相同的两个城市。每条道路都是双向的。城市编号从 #cf_span[1] 到 #cf_span[n]。贝兰的道路网络可能不连通。\n\n## Output\n\n第一行输出 #cf_span[w] —— 最多可能的集数。接下来的 #cf_span[w] 行应以格式 #cf_span[x], #cf_span[y], #cf_span[z] 输出每集内容，这三个整数表示巫师访问城市的顺序。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $.  \nEach edge $ e \\in E $ is bidirectional and may be traversed at most once in either direction.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ 0 \\leq m \\leq 2 \\cdot 10^5 $  \n3. No multiple edges; simple graph.  \n\n**Objective**  \nFind the maximum number $ w $ of edge-disjoint walks (episodes) such that:  \n- Each walk is a sequence of vertices $ (x, y, z) $, corresponding to traversing two consecutive edges: $ x \\to y \\to z $.  \n- Each edge in $ E $ is used in at most one walk (in either direction).  \n- Walks may share vertices but not edges.  \n- Maximize $ w $, the total number of such 2-edge walks.  \n\n**Note**: Each episode consumes exactly two edges (forming a path of length 2). The problem reduces to decomposing the graph into the maximum number of edge-disjoint paths of length 2.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF860D","tags":["dfs and similar","graphs","greedy"],"sample_group":[["4 5\n1 2\n3 2\n2 4\n3 4\n4 1","2\n1 4 2\n4 3 2"],["5 8\n5 3\n1 2\n4 5\n5 1\n2 5\n4 3\n1 4\n3 2","4\n1 4 5\n2 3 4\n1 5 3\n5 2 1"]],"created_at":"2026-03-03 11:00:39"}}