#PU916. USACO 2019 February Contest, Bronze — Problem 2. The Great Revegetation

    ID: 1387 传统题 文件IO:revegetate 2000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>USACO赛事:feb19来源:usaco.orgscoring:equal_test_cases贪心

USACO 2019 February Contest, Bronze — Problem 2. The Great Revegetation

USACO 2019 February Contest, Bronze — Problem 2. The Great Revegetation

题目描述

A lengthy drought has left Farmer John's NN pastures devoid of grass. However, with the rainy season arriving soon, the time has come to "revegetate". In Farmer John's shed, he has four buckets, each with a different type of grass seed. He wishes to sow each pasture with one of these types of seeds. Being a dairy farmer, Farmer John wants to make sure each of his cows has a varied diet. Each of his MM cows has two favorite pastures, and he wants to be sure different types of grass are planted in each, so every cow can choose between two types of grass. Farmer John knows that no pasture is a favorite of more than 33 cows. Please help Farmer John choose a grass type for each pasture so that the nutritional needs of all cows are satisfied.

输入格式

The first line of input contains NN (2≤N≤1002 \leq N \leq 100) and MM (1≤M≤1501 \leq M \leq 150). Each of the next MM lines contains two integers in the range 1…N1 \ldots N, describing the pair of pastures that are the two favorites for one of Farmer John's cows.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 6
4 1
4 2
4 3
2 5
1 2
1 5
12133
Problem credits: Dhruv Rohatgi