SPOJ.com - Problem INDISET

INDISET - Find all independent nodes

no tags

Let G be a graph with a set of n nodes and a set of m edges. An independent set I is a subset of nodes, no two nodes of which are connected by any edge in G.

A maximal independent set is an independent set such that adding any other node to the set forces the set to contain at least two nodes connected by an edge in G.

In this task, you are given a undirected graph as the input, and you have to find as many as possible independent nodes within the time limit. Your score is the total number of independent nodes found in all test cases.

Input

The first line contains two integers, n and m, representing the numbers of nodes and edges in the graph. 3 ≤ n ≤ 2000 and 3 ≤ m ≤ 40000. The nodes are numbered 1..n, but not necessarily in any order. The next m lines contain pair of integers representing edges between two nodes. The list of edges are not in any particular order.

Output

There should be one line output listing all valid independent nodes you found in the graph. The nodes are separated by one space.

Example

Input:
6 7
1 2
1 5
2 3
2 5
3 4
3 6
5 6

Output:
1 4 6

Submit solution!

hide comments



	smittal12: 2016-02-28 08:56:48 First I got 592 marks then 707 still leaderboard is showing 592... Can anyone explain this?
	Jimmy Tirtawangsa: 2012-08-26 09:15:19 Hi Tjandra salam kenal. Mungkin cuma sedikit yang berani karena disangka problemnya sangat susah karena problem klasik.
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2012-07-11 09:42:54 Note: I know that Jimmy Tirtawangsa understand Indonesian language. @Jimmy Tirtawangsa: Wah... Problem yang sangat bagus, baru ada 3 orang yang berhasil memecahkannya, dan aku berada di urutan ke2. Keren juga ya kalau bisa buat problem dengan aturan judge sendiri. Sebenarnya saya juga problemsetter di SPOJ, tapi belum sampai bisa bikin judge sendiri. Ok, saya tunggu problem berikutnya ya... ;)
	Nikolay Nedelchev: 2012-05-08 11:03:37 ok, 10x no, strange things were before the correction
	Jimmy Tirtawangsa: 2012-05-08 00:39:45 No you can't, but it's somewhat correlated to the graph size. I set longer time limit for bigger graph. Looking at your result, you no need to worry about the time limit as your program runs well below the time limit. Which strange things that you see? After the correction of the judge, I think the result is ok. Previously you output same nodes multiple times, and the judge incorrectly counts them accumulatively. Now it is regarded as a wrong answer.
	Nikolay Nedelchev: 2012-05-07 18:32:05 And how do we know about which test case, which time limit is valid? ps I also noticed strange things in the judgment
	Jimmy Tirtawangsa: 2012-05-07 12:45:05 There are several datasets. Each is given its own time limit. ps. There is some errors in judging. All submisssions have been rejudged.
	Nikolay Nedelchev: 2012-05-06 23:19:41 what means : Time limit : 1s-9s ?

Submit solution!

Added by:	Jimmy Tirtawangsa
Date:	2012-04-17
Time limit:	0.200s-1.799s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 GAWK BASH BF
Resource:	http://en.wikipedia.org/wiki/Independent_set_(graph_theory)