P1694 [USACO19FEB] The Great Revegetation B

A long drought has left Farmer John’s $N$ pastures short of grass. With the rainy season coming soon, now is the time to replant. Farmer John has four buckets in his barn, each containing a different type of grass seed. He wants to plant exactly one type of grass in each pasture. As a dairy farmer, Farmer John wants to make sure each of his cows gets a varied diet. Each of his $M$ cows has two favorite pastures, and he wants to ensure that these two pastures are planted with different types of grass, so that each cow has two choices of grass. Farmer John knows that no pasture is liked by more than $3$ cows. Please help Farmer John choose the grass type for each pasture so that all cows’ needs are satisfied.

The first line of input contains $2 \leq N \leq 100$ and $1 \leq M \leq 150$. The next $M$ lines each contain two integers in the range $1 \dots N$, representing the two pastures liked by one of Farmer John’s cows.

Output an $N$-digit number, where each digit is one of $1 \ldots 4$, indicating the type of grass planted in each pasture. The first digit corresponds to the grass type in pasture $1$, the second digit to pasture $2$, and so on. If there are multiple feasible solutions, output the smallest $N$-digit number among all solutions.

Translated by ChatGPT 5