codeforces638C. Road Improvement【dfs】
C. Road Improvement time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output
In Berland there are n cities and n - 1 bidirectional roads. Each road connects some pair of cities, from any city you can get to any other one using only the given roads.
In each city there is exactly one repair brigade. To repair some road, you need two teams based in the cities connected by the road to work simultaneously for one day. Both brigades repair one road for the whole day and cannot take part in repairing other roads on that day. But the repair brigade can do nothing on that day.
Determine the minimum number of days needed to repair all the roads. The brigades cannot change the cities where they initially are.
InputThe first line of the input contains a positive integer n (2 ≤ n ≤ 200 000) — the number of cities in Berland.
Each of the next n - 1 lines contains two numbers ui, vi, meaning that the i-th road connects city ui and city vi (1 ≤ ui, vi ≤ n, ui ≠ vi).
OutputFirst print number k — the minimum number of days needed to repair all the roads in Berland.
In next k lines print the description of the roads that should be repaired on each of the k days. On the i-th line print first number di — the number of roads that should be repaired on the i-th day, and then di space-separated integers — the numbers of the roads that should be repaired on the i-th day. The roads are numbered according to the order in the input, starting from one.
If there are multiple variants, you can print any of them.
Examples input4
1 2
3 4
3 2
output 2
2 2 1
1 3
input 6
3 4
5 4
3 2
1 3
4 6
output 3
1 1
2 2 3
2 4 5
Note In the first sample you can repair all the roads in two days, for example, if you repair roads 1 and 2 on the first day and road 3 — on the second day.
题意：N个城市给出城市间的连通关系，在每个城市有一个修路队修复一条路需要这条路相连的两个城市的修路队同时工作一天，问最少需要多少天能修复所有的路
一个城市修路时与其相连的其他城市都不能再与该城市在同一天修路dfs即可。
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=200010;
vectorans[maxn];
vector >G[maxn];
int num=0;
void dfs(int now,int pre,int cnt){int day=0;for(int i=0;i
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！