English · Original
Chinese · Translation
Formal · Original
Sergey just turned five years old! When he was one year old, his parents gave him a number; when he was two years old, his parents gave him an array of integers. On his third birthday he received a string. When he was four, his mother woke him up in a quiet voice, wished him to be a good boy and gave him a rooted tree. Today he celebrates his birthday again! He found a directed graph without loops as a present from his parents.
Since Sergey is a very curious boy, he immediately came up with a thing to do. He decided to find a set $Q$ of vertices in this graph, such that no two vertices $x, y \in Q$ are connected by an edge, and it is possible to reach any vertex $z \notin Q$ from some vertex of $Q$ in no more than two moves.
After a little thought, Sergey was able to solve this task. Can you solve it too?
A vertex $y$ is reachable from a vertex $x$ in at most two moves if either there is a directed edge $(x,y)$, or there exist two directed edges $(x,z)$ and $(z, y)$ for some vertex $z$.
## Input
The first line of input contains two positive integers $n$ and $m$ ($1 \le n \le 1\,000\,000$, $1 \le m \le 1\,000\,000$) — the number of vertices and the number of edges in the directed graph.
Each of the following $m$ lines describes a corresponding edge. Each one contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$) — the beginning and the end of the $i$\-th edge. The graph may contain multiple edges between the same pair of vertices.
## Output
First print the number $k$ — the number of selected vertices. Then print $k$ distinct integers — the indices of the selected vertices.
If multiple answers exist you can output any of them. In particular, you don't have to minimize the number of vertices in the set. It is guaranteed, that there is always at least one valid set.
[samples]
## Note
In the first sample, the vertices $1, 3, 4, 5$ are not connected. The vertex $2$ is reachable from vertex $1$ by one edge.
In the second sample, it is possible to reach the vertex $1$ in one move and the vertex $2$ in two moves.
The following pictures illustrate sample tests and their answers.
<center> </center>
Sergey 刚满五岁！当他一岁时，父母给了他一个数字；两岁时，父母给了他一个整数数组；三岁生日时，他收到一个字符串；四岁时，母亲轻声唤醒他，祝他做个好孩子，并给了他一棵有根树。今天他又庆祝生日了！他从父母那里收到了一个无环有向图。
由于 Sergey 是一个非常好奇的男孩，他立刻想到了要做一件事。他决定在这个图中找到一个顶点集合 $Q$，使得 $Q$ 中任意两个顶点 $x, y$ 之间没有边相连，并且对于任意不在 $Q$ 中的顶点 $z$，都能从 $Q$ 中的某个顶点在不超过两步内到达 $z$。
经过一番思考，Sergey 成功解决了这个问题。你也能解决吗？
顶点 $y$ 可以从顶点 $x$ 在至多两步内到达，当且仅当：存在一条有向边 $(x, y)$，或者存在两个有向边 $(x, z)$ 和 $(z, y)$，其中 $z$ 是某个顶点。
输入的第一行包含两个正整数 $n$ 和 $m$（$1 lt.eq n lt.eq 1 thin 000 thin 000$，$1 lt.eq m lt.eq 1 thin 000 thin 000$）—— 分别表示有向图的顶点数和边数。
接下来的 $m$ 行每行描述一条边，包含两个整数 $a_i$ 和 $b_i$（$1 lt.eq a_i, b_i lt.eq n$，$a_i != b_i$）—— 分别表示第 $i$ 条边的起点和终点。图中可能包含连接同一对顶点的多条边。
首先输出一个整数 $k$ —— 所选顶点的数量。然后输出 $k$ 个互不相同的整数 —— 所选顶点的编号。
如果有多个答案，输出任意一个即可。特别地，你不需要最小化集合中顶点的数量。题目保证至少存在一个合法集合。
在第一个样例中，顶点 $1, 3, 4, 5$ 互不相连。顶点 $2$ 可以通过一条边从顶点 $1$ 到达。
在第二个样例中，顶点 $1$ 可以在一步内到达，顶点 $2$ 可以在两步内到达。
下图展示了样例测试及其答案。
## Input
输入的第一行包含两个正整数 $n$ 和 $m$（$1 lt.eq n lt.eq 1 thin 000 thin 000$，$1 lt.eq m lt.eq 1 thin 000 thin 000$）—— 分别表示有向图的顶点数和边数。接下来的 $m$ 行每行描述一条边，包含两个整数 $a_i$ 和 $b_i$（$1 lt.eq a_i, b_i lt.eq n$，$a_i != b_i$）—— 分别表示第 $i$ 条边的起点和终点。图中可能包含连接同一对顶点的多条边。
## Output
首先输出一个整数 $k$ —— 所选顶点的数量。然后输出 $k$ 个互不相同的整数 —— 所选顶点的编号。如果有多个答案，输出任意一个即可。特别地，你不需要最小化集合中顶点的数量。题目保证至少存在一个合法集合。
[samples]
## Note
在第一个样例中，顶点 $1, 3, 4, 5$ 互不相连。顶点 $2$ 可以通过一条边从顶点 $1$ 到达。
在第二个样例中，顶点 $1$ 可以在一步内到达，顶点 $2$ 可以在两步内到达。
下图展示了样例测试及其答案。
**Definitions**
Let $ G = (V, E) $ be a directed graph with $ n = |V| $ vertices and $ m = |E| $ edges, where $ V = \{1, 2, \dots, n\} $ and $ E \subseteq V \times V $, with no self-loops (i.e., $ (v, v) \notin E $ for all $ v \in V $).
Let $ Q \subseteq V $ be a subset of vertices.
**Constraints**
1. **Independence**: For all $ x, y \in Q $, $ (x, y) \notin E $ and $ (y, x) \notin E $.
2. **2-Reachability**: For every vertex $ z \in V \setminus Q $, there exists some $ x \in Q $ such that $ z $ is reachable from $ x $ in at most two directed edges. That is, either:
- $ (x, z) \in E $, or
- there exists $ w \in V $ such that $ (x, w) \in E $ and $ (w, z) \in E $.
**Objective**
Find any subset $ Q \subseteq V $ satisfying the above two constraints.
API Response (JSON)
{
"problem": {
"name": "C. Sergey's problem",
"description": {
"content": "Sergey just turned five years old! When he was one year old, his parents gave him a number; when he was two years old, his parents gave him an array of integers. On his third birthday he received a st",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1019C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Sergey just turned five years old! When he was one year old, his parents gave him a number; when he was two years old, his parents gave him an array of integers. On his third birthday he received a st...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Sergey 刚满五岁！当他一岁时，父母给了他一个数字；两岁时，父母给了他一个整数数组；三岁生日时，他收到一个字符串；四岁时，母亲轻声唤醒他，祝他做个好孩子，并给了他一棵有根树。今天他又庆祝生日了！他从父母那里收到了一个无环有向图。\n\n由于 Sergey 是一个非常好奇的男孩，他立刻想到了要做一件事。他决定在这个图中找到一个顶点集合 $Q$，使得 $Q$ 中任意两个顶点 $x, y$ 之间没有边相...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ G = (V, E) $ be a directed graph with $ n = |V| $ vertices and $ m = |E| $ edges, where $ V = \\{1, 2, \\dots, n\\} $ and $ E \\subseteq V \\times V $, with no self-loops (i.e., $ (...",
"is_translate": false,
"language": "Formal"
}
]
}