Skip to content

11098: 【原1098】OddGraph



author: Jiejun Zhang 原OJ链接:


Pangzi looks somehow odd recently. He started to love odd things, like odd numbers and odd graphs. He says, an odd graph is a non-empty graph (that is the set of vertices is non-empty) that every vertex has an odd degree (that is, connected to an odd number of edges). If a graph is not odd, he will try to find a subgraph that is odd. In Pangzi's mind, a subgraph of a graph G=(V, E) is composed by some vertices in G and all edges between these vertices from G. Mathematically, G'=(V', E') where V' is a subset of V and E'={(u, v): u, v in V' and (u, v) in E}.

Now Pangzi will give you a graph, please tell him if this graph is odd. If it is not odd, try to find an odd subgraph.

Pay attention. As Pangzi is odd now, when he talks about graphs, he is actually talking about undirected graphs.

Input Format

The first line of the input is an integer T (T <= 100), indicating the number of test cases.

Then, T test cases follow. For every test case, the first line is 2 integers n, m (1 <= n <= 100, 0 <= m <= 1000). Then m lines follow, every line contains 2 integers u, v (1<=u, v<=n) indicating an edge in G.

There is no self-loop or parallel edge.

Output Format

Output the answer for each test case.

  • If the graph is an odd graph, output "ODD GRAPH".
  • If the graph is not odd and contains an odd subgraph, output the subgraph in the following format. First output a number K, the vertices in this subgraph, and then output K integers in increasing order representing the vertices. These numbers should be printed in one line and separated by one space. No extra spaces. If there are multiple solutions, first minimize K, and if there are still multiple solutions, output the lexicographically smallest sequence of vertices.
  • If the graph is not odd and contains no odd subgraph, output "NO ODD SUBGRAPH"

For two sequences a[1], a[2], ..., a[K] and b[1], b[2], ..., b[k], a is lexicographically smaller than b if and only if for the smallest i such that a[i] != b[i], a[i] < b[i].

See the sample output for clarifications.

Sample Input

1 0
4 4
1 2
2 3
3 4
4 1
2 1
1 2

Sample Output

2 1 2

Case Limits

Time limit: 500 msec

Memory limit: 64 MB

Oops! 本题目还没有解答!