Задача . F. Дороги и рамен

В стране Огня есть \(n\) деревень и \(n-1\) двусторонняя дорога, причем из каждой деревни можно добраться в каждую по дорогам. В этой стране есть только два типа дорог: каменные и песчаные. Поскольку страна Огня очень прогрессивная и постоянно обновляется, то каждый день рано утром строители выбирают одну дорогу и меняют ее тип (с каменной на песчаную или наоборот). А еще в стране Огня все любят рамен, поэтому каждый день на каждой каменной дороге устанавливается одна палатка с раменом, а в конце дня палатку убирают.

В течение каждого из ближайших \(m\) дней, после того как очередную дорогу переделают, Наруто и Джирайя выбирают себе простой маршрут по стране Огня. Их маршрут может начинаться с любой деревни и заканчиваться тоже в любой (возможно, той же), но по каждой дороге они могут проходить не более одного раза. Поскольку Наруто и Джирайя очень любят рамен, то на каждой каменной дороге они обязательно покупают ровно одну тарелку рамена и кто-нибудь один из них ее ест. Поскольку у ниндзя все должно быть честно, то они выбирают только те пути, проходя по которым они могут съесть равное количество тарелок с раменом. Наруто и Джирайя любят много путешествовать, поэтому каждый день они выбирают самый длинный путь из подходящих. Для каждого дня необходимо определить максимальную длину пути (то есть количество дорог в нём), которым могут пойти Наруто и Джирайя.