## UTS Open '21 P4 - Lucky Graph

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Allen has a simple undirected graph (no self loops or parallel edges) with nodes and 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 to maximize its lucky score. As a friend of Allen, tell him the maximum possible lucky score of 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.

#### Input Specification

The first line contains integers and , the number of nodes and edges in respectively.

The next lines each contain integers and , the endpoints of the edge.

#### Output Specification

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

On the second line output an integer , the number of edges to remove.

On the third line output integers , the indices of the edges to be removed. All 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. must be the maximum possible lucky score.
3. The graph must achieve a lucky score of 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 and have odd degree, so the lucky score of this graph is . 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 and it is obviously the maximum possible lucky score. Note that not removing any edges would also be a valid solution.