COCI '21 Contest 3 #2 Cijanobakterije

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Young microbiologist Maja is making a microscopic Christmas tree out of a species of cyanobacteria called Stigonema arboreus. This species is known for its colonies made from individual cells which link together, forming a tree graph. More precisely, for each pair of cyanobacteria in the colony, there is a unique path through the colony from one cyanobacterium to the other.

Maja wants her Christmas tree colony to contain a chain of cyanobacteria that is as long as possible. A chain is determined by a sequence of cyanobacteria, where each cyanobacterium appears at most once, and every pair of adjacent cyanobacteria are directly linked together. Because none of the colonies she currently has is long enough, Maja will have to connect some of the colonies together. She does this by repeatedly choosing two cyanobacteria from different colonies, bringing them close to each other, and joining them with superglue. Since the bacteria are sensitive to cycles, Maja has to be careful not to join two bacteria from the same colony at any time. Using a series of such gluing procedures, Maja wants to obtain a colony that contains the longest possible chain.

Maja is tired from using her microscope, and there are a lot of cyanobacteria. Help Maja determine the length of the longest chain of cyanobacteria she could obtain by connecting the colonies. The length of a chain is determined by the number of cyanobacteria from which it is formed.

Input Specification

The first line contains positive integers n and m (1 \le n \le 100\,000, 0 \le m < n), the number of cyanobacteria and the number of direct connections between them.

The following m lines contain a pair of positive integers a_i and b_i (1 \le a_i, b_i \le n), which denote that the bacteria a_i and b_i are directly linked. No bacterium is directly linked to itself, and no connection will be listed more than once.

The connections are such that the bacteria form some colonies, each of which is a tree.

Output Specification

In the only line, print the largest possible length of a chain in the final colony.


115m = n-1
26b_i = a_i+1 for each i = 1, \dots, m
361 \le a_i \le 2 for each i = 1, \dots, m
4151 \le n \le 1000
528No additional constraints.

Sample Input 1

100 0

Sample Output 1


Sample Input 2

8 6
1 2
1 3
1 4
5 6
5 7
5 8

Sample Output 2


Explanation for Sample Output 2

In the second example, there are two colonies of cyanobacteria. In the first colony, all cyanobacteria are directly connected to cyanobacterium 1, and in the second with cyanobacterium 5. If any two cyanobacteria except 1 and except 5 are connected, the resulting colony will contain the longest possible chain. E.g., if 2 and 6 are connected, one such chain will be 3 \to 1 \to 2 \to 6 \to 5 \to 7, which has length 6.

Sample Input 3

6 5
1 2
2 3
3 4
4 6
4 5

Sample Output 3



There are no comments at the moment.