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.



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.


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



4 4

1 2

3 2

4 3

2 1



1 2

hide comments
below_average: 2021-07-10 13:19:58

nice problem

lakshya1st: 2021-05-17 15:24:30

Same as TOUR only difference is find outdegree instead of indegree in this problem..!! SCC :)

saurabh_kl: 2021-02-26 18:41:17

A nice problem

ya_ali313: 2021-01-14 19:09:08

dont forget: you should print candidate cities in increasing order.

goa_baba: 2020-05-14 21:40:27

Poor test Cases Framed
Wont work where there is not a single candidate City
For eg: test case:
8 6
1 2
2 3
3 4
5 4
6 7
8 7
: It'a answer should be 0

shafwanur010: 2020-03-30 18:06:37

Remember -
1. Sort components in INCREASING order.
2. There might be duplicate edges, adding edges only when there isn't an edge between vertex u and v did the trick. (This is a major test data flaw)

Also, the test data is wrong. There might be multiple sccs. Then the answer would be to consider each scc as a node, form a tree and output the root of the tree. I found just an scc with max size and outputted it in increasing order and got AC. This isn't right.

aryan12: 2020-03-12 22:51:57

AC in 2 gos. Saved by .01 seconds from a TLE. #0.99 #LuckFavoursMe

daihandsome: 2020-03-12 09:25:35

time limit on test 20 bruh bruh:<

coolio_1: 2020-03-05 03:00:10

AC in 1 go. Took a lot of effort.

sangmai: 2020-02-21 10:50:36

I believe that there are duplicated edges in test case 20. AC after handling that case.

Added by:Narek Saribekyan
Time limit:1s-4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:Armenian TST 2010, Round 2