레이팅 미적용농부 존에게는 편의상 1...N으로 번호가 붙은 N개의 목초지(1 <= N <= 50,000)가 있고, 이들은 M개의 양방향 길(1 <= M <= 100,000)로 연결되어 있다. 길 i는 목초지 A_i와 목초지 B_i를 연결하며 A_i != B_i이다. 두 길이 같은 목초지 쌍을 연결할 수도 있다.
베시는 각 목초지에 문자 'F' 또는 'J'가 적힌 큰 표지판을 세우고 싶은데, FJ가 혼란스러워하지 않도록 길로 연결된 두 목초지에는 반드시 서로 다른 문자가 걸리게 하려고 한다.
표지판 업체는 'F' 표지판에 'J' 표지판보다 더 많은 요금을 청구하므로, 베시는 사용하는 'J' 표지판의 수를 최대화하려고 한다. 이 수를 구하거나, 표지판을 올바르게 배치하는 방법이 없으면 -1을 출력한다.
첫째 줄: 두 정수 N과 M이 주어진다.
둘째 줄부터 M+1째 줄까지: A_i에서 B_i로 가는 양방향 길이 있음을 나타내는 두 정수 A_i와 B_i가 주어진다.
베시가 사용할 수 있는 'J' 표지판의 최대 수를 정수 하나로 출력한다. 올바른 해가 없으면 -1을 출력한다.
decorate.in · 출력을 쓸 파일 decorate.out4 4
1 2
2 3
3 4
4 12Output details: Bessie can label pastures 1 and 3 (or 2 and 4) with 'J' signs.
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > US Open > Bronze