TRIP2 - A Famous King’s Trip

no tags 

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 old that traffic jam often occurs. Unfortunately, Mr. B is now preparing for the ICPC World Final Contest so that he is quite busy. 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 has just 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 back to the palace. Moreover, during his travelling, the king must visit each city at least once too.

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

Input

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. Each of them denotes 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.

Output

For each test case, if Mr. B can satisfy the Kings requirement, then output YES in the first line, otherwise, output NO. If the answer is YES, output two integers X and Y (X < Y) in the following line, specifying 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.

Example

Input:
4 6
1 2
1 3
1 4
2 3
2 4
3 4

Output:
Case 1: YES
1 6

hide comments
Divyanshu Goyal: 2014-02-20 08:57:05

@problem setter can u give some more test cases

kojak_: 2012-07-26 23:37:55

You still have cases, Nehal.

Nehal J Wani: 2012-07-20 20:39:47

Since we don't have to scan for n test cases, why do we print "Case 1:" ?


Added by:Fudan University Problem Setters
Date:2012-05-25
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:lcosvse's own problem, used in FDU Local Contest 2012