题目描述

去掉两条边，使得剩下的图连通，且所有点度数都为偶数。

B先生是FDUCS王国的首席工程师。最近，国王要求B先生制定一个新的道路网络规划，因为现有的规划过时，经常出现交通堵塞。不幸的是，B先生最近一直在忙着准备ICPC世界决赛。因此，他请求他的朋友G先生和M先生帮助他完成这项工作。当B先生从朋友那里得到解决方案时，他意识到了一些问题：B先生忘记告诉G先生和M先生预算计划，因此新的解决方案包含了政府无法负担的太多新道路。经过精确计算，B先生发现根据财务情况，他只需要删除两条道路（当然，B先生不会删除超过两条道路，因为他希望国家的人民能够拥有方便的交通）。

B先生可以随意删除两条道路吗？答案是否定的。国王想要乘坐新的道路系统去审查B先生的工作。然而，国王很忙，不想进行不必要的旅行。换句话说，国王希望B先生设计一个道路系统，使他可以从宫殿（某个城市）出发，经过每条道路恰好一次，然后返回宫殿。此外，在他的旅行中，国王必须至少访问每个城市一次。

B先生觉得很难通过从原始设计中删除两条道路来满足国王的要求。作为一个潜力无限的ICPC候选人，你能帮助他吗？

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?

输入格式

对于每个测试用例，第一行包含两个整数 $n$ 和 $m$，表示王国中的城市数量和B先生原始计划中的道路数量。接下来是 $m$ 行，每行包含一对整数 $a$ 和 $b$，表示城市 $a$ 和城市 $b$ 之间有一条双向道路（$1 \le a, b \le n$，且 $a \ne b$），城市编号从 $1$ 开始。没有两条道路连接相同的一对城市。

For each test case, the first line contains two integers, $n$ and $m$, 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\le a,b\le n$ and $a\ne b$), the number of cities are counted from $1$. No two roads connect the same pair of cities.

输出格式

对于每个测试用例，如果B先生可以满足国王的要求，输出“YES”；否则输出“NO”。如果答案是“YES”，则在下一行输出两个整数 $x$ 和 $y$（$x < y$），指定B先生应该从原设计中删除的两条道路。 $x$ 和 $y$ 是从输入中道路的索引，从 $1$ 开始计数。如果有多个可能的答案，输出使得 $(x, y)$ 字典序最小的答案。

For each test case, if Mr. B can satisfy the King’s 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 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.

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Case 1: YES 
1 6

数据规模与约定

对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5$。