CAPCITY - Capital City


There are N cities in Flatland connected with M unidirectional roads. The cities are numbered from 1 to N. The Flat Circle of Flatland (FCF) wants to set up a new capital city for his kingdom. For security reasons, the capital must be reachable from all other cities of Flatland. FCF needs the list of all candidate cities. You are the chief programmer at FACM (Flat Association for Computing Machinery) responsible for providing the list to FCF as soon as possible.

Input

 

The first line of the input file contains two integers։ 1N≤100,000 and 1M≤200,000. Each of the following M lines contains two integers 1A, B≤N denoting a road from A to B.


Output 


The output file contains an integer denoting the number of candidate cities followed by the list of candidate cities in increasing order.


Example


Input:


4 4

1 2

3 2

4 3

2 1


Output:


2

1 2


hide comments
botanich: 2017-09-14 17:28:10

@scorpion_ajay pls tell me where writen about its no cases without any capital city? I cant find it

Last edit: 2017-09-14 17:45:15
pratham_1: 2017-09-11 21:53:57

Bad time limit for java ;(

scorpion_ajay: 2017-07-04 14:27:16

WA on test case 20, why?????

scorpion_ajay: 2017-07-04 11:57:50

@karan_batra it can not be a test case when there is no capital city, read the question carefully!!

satylogin: 2017-06-25 09:58:47

I really don't know what is the problem with spoj... This happened third time. For storing edge, I declared array size as 100001 instead of 200001 and then instead of giving SIGSEV or RE, it gives WA... wasted a lot of time to look for answer and then just changed the lim and got accepted. If anyone knows why this happens please tell me.. Thanks in advance.

Kushal Saharan: 2017-06-16 11:54:03

Be careful that the indexing for the cities is 1-based and NOT 0-based. Costed in uncountable WA/RTE and loads of time.

steady_bunny: 2017-06-15 14:12:33

@noob909
for input:
4 5
1 2
3 2
4 3
2 1
3 4
output will be:
2
1 2
as
1-2 forms SCC
3-4 forms scc
3-4 is not reachable from 1-2
but 1-2 is reachable from 3-4 .

Last edit: 2017-06-15 14:14:16
ayush_1997: 2017-03-06 15:17:49

good question!!

karan_batra: 2017-01-06 15:52:51

Weak test cases. No test case when there is no capital city.

hamjosh1: 2016-11-13 10:51:38

Use fast IO costed me TLE


Added by:Narek Saribekyan
Date:2010-06-20
Time limit:0.210s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Armenian TST 2010, Round 2