{"raw_statement":[{"iden":"statement","content":"A long time ago in some country in Asia were civil wars.\n\nEach of _n_ cities wanted to seize power. That's why sometimes one city gathered an army and sent it to campaign against another city.\n\nRoad making was difficult, so the country had few roads, exactly _n_ - 1. Also you could reach any city from any other city going on those roads.\n\nEven during the war the Oriental people remain spiritually rich and appreciate the beauty of nature. And to keep the memory of this great crusade for the centuries to come, they planted one beautiful tree by the road on which the army spent most time. The Oriental people love nature, that's why if there were several such roads, then one tree was planted by each of them.\n\nRecently, when the records of the war were found, it became clear that each city attacked each other one exactly once. There were exactly _n_(_n_ - 1) attacks in total. Everyone has been wondering what road after those wars became the most beautiful, that is, by which road they planted the largest number of beautiful trees."},{"iden":"input","content":"The first line contains an integer _n_ (2 ≤ _n_ ≤ 105), which represents the number of cities. Next _n_ - 1 lines contain three integers each: the numbers of cities _a__i_, _b__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_), connected by the _i_\\-th road and the number of days _d__i_ the army spends to go on it (1 ≤ _d__i_ ≤ 109). The lengths of several roads may coincide."},{"iden":"output","content":"Print on the first line two integers — the number of beautiful trees on the most beautiful road and the number of the most beautiful roads. Print on the second line the list of the most beautiful roads in the sorted order by the numbers' increasing. The roads are numbered from 1 to _n_ - 1 in the order in which they are given in the input data.\n\nPlease, do not use _%lld_ specificator to write 64-bit integers in C++. It is preferred to use the _cout_ stream (also you may use the _%I64d_ specificator)."},{"iden":"examples","content":"Input\n\n2\n2 1 5\n\nOutput\n\n2 1\n1 \n\nInput\n\n6\n1 2 1\n1 3 5\n3 4 2\n3 5 3\n3 6 4\n\nOutput\n\n16 1\n2"}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"很久以前，在亚洲的一个国家爆发了内战。\\n\\n每个城市都希望夺取权力，因此有时一个城市会集结军队，派兵攻打另一个城市。\\n\\n修建道路十分困难，因此这个国家只有很少的道路，恰好有 #cf_span[n - 1] 条。并且通过这些道路，你可以从任意一个城市到达另一个城市。\\n\\n即使在战争期间，东方人民依然精神富足，热爱自然之美。为了将这场伟大远征的记忆流传后世，他们在军队花费时间最长的道路上种植了一棵美丽的树。由于东方人民热爱自然，如果存在多条这样的道路，则每条道路上都种植一棵树。\\n\\n最近，当战争的记录被发现时，人们清楚地了解到，每个城市都恰好攻击了其他每个城市一次，总共发生了 #cf_span[n(n - 1)] 次攻击。人们一直好奇，在这些战争之后，哪条道路变得最为美丽，即哪条道路上种植了最多的美丽树木。\\n\\n第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 105])，表示城市的数量。接下来的 #cf_span[n - 1] 行每行包含三个整数：由第 #cf_span[i] 条道路连接的两个城市编号 #cf_span[ai, bi] (#cf_span[1 ≤ ai, bi ≤ n])，以及军队通过该道路所花费的天数 #cf_span[di] (#cf_span[1 ≤ di ≤ 109])。若干条道路的长度可能相同。\\n\\n请在第一行输出两个整数——最美丽道路上的美丽树木数量，以及最美丽道路的数量。在第二行按编号递增的顺序输出所有最美丽道路的编号。道路编号从 #cf_span[1] 到 #cf_span[n - 1]，按输入顺序编号。\\n\\n请勿在 C++ 中使用 _%lld_ 格式说明符输出 64 位整数。推荐使用 _cout_ 流（也可以使用 _%I64d_ 格式说明符）。\"}, {\"iden\":\"input\",\"content\":\"第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 105])，表示城市的数量。接下来的 #cf_span[n - 1] 行每行包含三个整数：由第 #cf_span[i] 条道路连接的两个城市编号 #cf_span[ai, bi] (#cf_span[1 ≤ ai, bi ≤ n])，以及军队通过该道路所花费的天数 #cf_span[di] (#cf_span[1 ≤ di ≤ 109])。若干条道路的长度可能相同。\"}, {\"iden\":\"output\",\"content\":\"请在第一行输出两个整数——最美丽道路上的美丽树木数量，以及最美丽道路的数量。在第二行按编号递增的顺序输出所有最美丽道路的编号。道路编号从 #cf_span[1] 到 #cf_span[n - 1]，按输入顺序编号。请勿在 C++ 中使用 _%lld_ 格式说明符输出 64 位整数。推荐使用 _cout_ 流（也可以使用 _%I64d_ 格式说明符）。\"}, {\"iden\":\"examples\",\"content\":\"输入22 1 5输出2 11 输入61 2 11 3 53 4 23 5 33 6 4输出16 12 \"}]}","sample_group":[],"show_order":[],"formal_statement":"Let $ G = (V, E) $ be a tree with $ |V| = n $, $ |E| = n - 1 $. Each edge $ e_i \\in E $ (for $ i = 1, 2, \\dots, n-1 $) has a positive integer weight $ d_i $, representing the number of days an army spends traversing it.\n\nFor every ordered pair of distinct cities $ (u, v) \\in V \\times V $, $ u \\ne v $, an army travels from $ u $ to $ v $ along the unique simple path in $ G $. For each such journey, the edge $ e \\in E $ on the path that has **maximum weight** among all edges on that path receives one tree. If multiple edges on the path share the maximum weight, then **each** such edge receives one tree.\n\nLet $ t(e) $ denote the total number of trees planted on edge $ e $.\n\nDefine:\n- $ T_{\\max} = \\max_{e \\in E} t(e) $: the maximum number of trees on any single road.\n- $ R = \\{ e \\in E \\mid t(e) = T_{\\max} \\} $: the set of most beautiful roads.\n\n**Objective:**  \nCompute $ T_{\\max} $, $ |R| $, and the sorted list of indices $ i $ (from input order) of edges in $ R $.\n\n---\n\n**Formal Input:**  \n- $ n \\in \\mathbb{Z} $, $ 2 \\leq n \\leq 10^5 $  \n- $ n - 1 $ edges: each $ e_i = (a_i, b_i, d_i) $, with $ a_i, b_i \\in [1, n] $, $ d_i \\in \\mathbb{Z}^+ $, $ 1 \\leq d_i \\leq 10^9 $\n\n**Output:**  \n- First line: $ T_{\\max} $ and $ |R| $  \n- Second line: sorted list of indices $ i $ (1-based) of edges in $ R $\n\n---\n\n**Note:** The number of attacks is $ n(n-1) $, corresponding to all ordered pairs $ (u, v) $, $ u \\ne v $.","simple_statement":null,"has_page_source":false}