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
ashishgup: 2018-09-18 22:44:31

20th test case for me was not printing the cities in increasing order :(

preet_t: 2018-08-29 08:09:23

can also be solved using Kosaraju's algo.

m__sharma: 2018-08-14 09:58:49

TLE even after using TARJAN ! any hint?

shahianshu: 2018-08-13 10:02:54

nice question based on tarjan's algorithm , keep in mind that you can easily break away when you get 1st scc as it will give the required answer and then sort all the elements of the scc and then print them
anshushahi98@gmail.com

jalaikontum: 2018-07-23 11:20:05

AC in one go :))
tarjan algorithm :v, sorry for my bad english :v

s_a_k_s_h_a_m: 2018-07-14 11:57:02

use condensation of graph
sort the vertices in toplogical order(after reversing edges of condensed graph)

jh0n_12358: 2018-06-27 15:33:05

After 3 hours AC in one go

aditya12legend: 2018-06-23 17:07:47

Done with a combination of DSU and DFS

aman_sachin200: 2018-06-17 21:06:13

Awesome One!!!!Don't forget to print the cities in increasing order!!!!Similar problem TOUR !!:P

ankitraj7217: 2018-06-06 08:33:21

Weak test cases..No test cases for 0 capital city..

Last edit: 2018-06-06 08:41:55

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