[FDU2012校赛] A Famous King’s Trip

时间限制：5s 空间限制：128MB

题目描述

Mr. B is the chief engineer in the Kingdom of FDUCS. Recently, the King asks Mr. B to develop a new plan of the road network in the country, since the existing one is so outdated that traffic jam often occurs. Unfortunately, Mr. B is now busy preparing for the ICPC World Finals. Therefore, He asks his friends Mr. G and Mr. M to help him finish that work. When Mr. B gets the solution from his friends, he realizes some problems: Mr. B forgot to specify the budget plan to Mr. G and Mr. M, thus the new solution contains too many new roads which the government cannot afford. After a precise calculation, Mr. B finds that he only need to delete exactly two roads in term of the financial facts (Of course, Mr. B will not delete more than two roads because he wants people in his country to have a convenient traffic).

Can Mr. B delete two roads arbitrarily? The answer is negative. The King would like to take a travel on the new road system to review Mr. B's work. However, the King is so busy that he does not want to take travel with redundancy. That is, the King wants Mr. B to design a road system so that he can travel from the palace (in one city), pass each road exactly once, and then return to the palace. Moreover, during his travelling, the king must visit each city at least once.

Mr. B feels hard to satisfy the King’s demand by deleting two roads from the original design. As an ICPC candidate with unlimited potential, can you help him?

输入格式

For each test case, the first line contains two integers, n and m (1 <= n, m <= 200,000), indicating the number of cities in the Kingdom and the roads in Mr. B's original plan. Following this are m lines, each contains a pair of integers a and b, denoting a bidirectional road between city a and city b (1 <= a, b <= n and a != b), the number of cities are counted from 1. No two roads connect the same pair of cities.

输出格式

For each test case, if Mr. B can satisfy the King’s requirement, then output “YES” in the first line, otherwise output “NO” (quotes for clarifying). If the answer is “YES”, output two integers X and Y (X < Y) in the following line, specifying the two roads that Mr. B should delete from the original design. X and Y are the indexes of roads in the input, counting from 1. If there are more than one possible answer, output the one that makes the pair of (X, Y) lexicographically smallest.

样例输入

样例输出

Case 1: YES 
1  6

提示

没有写明提示

题目来源

没有写明来源