- 33

## Statement

## Goal

Given a population size and a network of connections between its members, determine the breakdown of cluster sizes of the population.Imagine that each member of a population is one person. Now consider that one member of the population becomes "infected" by a virus. Provided a set of connections (i.e. "member A is linked to member B"), the subset of members of the population infected by the virus can be simulated (we will assume that transmission is guaranteed to occur between linked members). This subset is effectively like an "outbreak" of a virus.

Your job is to assess these subsets, or

**clusters**and provide the breakdown of the distribution of cluster sizes in the given population.

NOTE: All links are two-way (reciprocal), there are no one-way links.

Given a population size

`N`, with members indexed from

Input:

**Line 1:**A number,

`N`, of members of the population

**Line 2:**A number,

`L`, of links within the population

**Next L lines:**Two space-separated integers representing the indexes of two linked members of the population

Output: "cluster size" and "cluster count" for each cluster, separated by a space; in descending order of size.

**Line 1:**Two space-separated integers representing the size and frequency of the largest sized cluster.

**Line 2:**Two space-separated integers representing the size and frequency of the 2-nd largest sized cluster

... and so on:

**Last Line:**Two space-separated integers representing the size and frequency of the smallest sized cluster

Constraints:

`N`<=

Every member of the population belongs to a cluster even if its size is of 1 (a cluster with only one member).

Input

**Line 1 :**: the number

`n_people`of elements in the structure

**Line 2 :**: the number

`n_links`of existing relations between elements in the structure

**two integers**

`n_links`next lines :`i`and

`j`for two elements linked

Output

The distribution of clusters in descending order by size of cluster. Each lines containing two integers, "cluster size" and "cluster count" for this cluster size, separated by a space.

...

**Line 1 :**the size of the biggest clusters**space**the number of clusters of this size...

**Line n :**the size of the smallest clusters**space**the number of clusters of this sizeConstraints

**Number of people**

`n_people`<=

**Number of links**

`n_links`<

Example

Input

5 2 4 0 0 2

Output

3 1 1 2

A higher resolution is required to access the IDE