Skip to content

11098: 【原1098】OddGraph

题目

题目描述

author: Jiejun Zhang 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1098

Description

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

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

Sample Output

NO ODD SUBGRAPH
2 1 2
ODD GRAPH

Case Limits

Time limit: 500 msec

Memory limit: 64 MB

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!