Allen has a simple undirected graph (no self loops or parallel edges) ~G~ with ~N~ nodes and ~M~ edges. He calls a node lucky if it has odd degree, and he defines the lucky score of a graph to be the number of lucky nodes in it. Since Allen loves lucky graphs, he is even willing to remove some edges from his graph ~G~ to maximize its lucky score. As a friend of Allen, tell him the maximum possible lucky score of ~G~ after removing some (possibly all or none) edges from the graph, and give him a list of edges to remove that achieves this score.

Constraints

For this problem, you MUST pass the sample cases in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

~1 \le N \le 2 \times 10^5~

~0 \le M \le 2 \times 10^5~

~1 \le a_i, b_i \le N~

Subtask 1 [15%]

~1 \le N \le 20~

~0 \le M \le 20~

Subtask 2 [20%]

~1 \le N \le 20~

Subtask 3 [65%]

No additional constraints.

Input Specification

The first line contains ~2~ integers ~N~ and ~M~, the number of nodes and edges in ~G~ respectively.

The next ~M~ lines each contain ~2~ integers ~a_i~ and ~b_i~, the endpoints of the ~i^\text{th}~ edge.

Output Specification

On the first line output an integer ~S~, the maximum possible lucky score.

On the second line output an integer ~K~ ~(0 \le K \le M)~, the number of edges to remove.

On the third line output ~K~ integers ~u_j~ ~(1 \le u_j \le M)~, the indices of the edges to be removed. All ~u_j~ must be pairwise distinct.

Scoring

For each test case, your output should satisfy the following requirements:

1. Your output must strictly match the format given and heed the constraints above.
2. ~S~ must be the maximum possible lucky score.
3. The graph ~G~ must achieve a lucky score of ~S~ after removing the edges provided in your list.

If your output meets all of the requirements above, you will receive AC for that test case. Otherwise, you will receive WA.

Sample Input 1

4 3
1 2
2 4
4 1

Sample Output 1

2
2
1 3

Explanation for Sample 1

The removed edges are marked with a dashed pattern. Only nodes ~2~ and ~4~ have odd degree, so the lucky score of this graph is ~2~. It can be proven that no higher lucky score can be achieved, so this is a valid answer.

Sample Input 2

6 9
1 2
2 3
3 1
1 4
2 5
3 6
4 5
5 6
6 4

Sample Output 2

6
3
7 8 9

Explanation for Sample 2

The removed edges are marked with a dashed pattern. Since all nodes have odd degree, the lucky score of this graph is ~6~ and it is obviously the maximum possible lucky score. Note that not removing any edges would also be a valid solution.