Grass Planting Optimization

Farmer John faces a long drought that has left his $N$ pastures with little grass. With the rainy season approaching, it is time to replant the grass! In his storage shed, Farmer John has four buckets, each filled with a different type of grass seed. He wants to plant one type of grass in each pasture. However, each of his $M$ cows has two favorite pastures and must have the option of eating from two different types of grass. That is, for every cow, the two favorite pastures should be planted with different types of grass.

Additionally, you are given that no pasture is favored by more than 3 cows. Your task is to help Farmer John choose a grass type for each pasture (from 1 to 4) so that every cow's dietary requirement is satisfied.

Note: A valid solution is guaranteed to exist. If there are multiple valid assignments, any one will be accepted.

Mathematically, if we denote the grass type planted in pasture i as \(g_i\) (with \(1 \le g_i \le 4\)), and if cow j likes pastures a and b, then the requirement is:

[ \forall j: g_{a_j} \neq g_{b_j} ]

where \(a_j\) and \(b_j\) are the two pastures favored by cow j.

inputFormat

The input consists of multiple lines. The first line contains two integers N and M where N is the number of pastures and M is the number of cows. The next M lines each contain two integers representing the indices of the two favorite pastures of each cow.

For example:

3 3
1 2
2 3
1 3

outputFormat

Output N integers in a single line, where the i-th integer (1-indexed) represents the grass type assigned to the i-th pasture. The grass types are numbered from 1 to 4 and must be assigned such that for every cow, the two favorite pastures get different grass types.

sample

3 3
1 2
2 3
1 3

1 2 3