C. Online Courses In BSU

Codeforces

IDCF770C

Time2000ms

Memory256MB

Difficulty—

dfs and similargraphsimplementation

English · Original

Chinese · Translation

Formal · Original

Now you can take online courses in the Berland State University! Polycarp needs to pass _k_ **main** online courses of his specialty to get a diploma. In total _n_ courses are availiable for the passage. The situation is complicated by the dependence of online courses, for each course there is a list of those that must be passed before starting this online course (the list can be empty, it means that there is no limitation). Help Polycarp to pass the least number of courses in total to get the specialty (it means to pass all **main** and necessary courses). Write a program which prints the order of courses. Polycarp passes courses consistently, he starts the next course when he finishes the previous one. Each course can't be passed more than once. ## Input The first line contains _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 105) — the number of online-courses and the number of main courses of Polycarp's specialty. The second line contains _k_ distinct integers from 1 to _n_ — numbers of main online-courses of Polycarp's specialty. Then _n_ lines follow, each of them describes the next course: the _i_\-th of them corresponds to the course _i_. Each line starts from the integer _t__i_ (0 ≤ _t__i_ ≤ _n_ - 1) — the number of courses on which the _i_\-th depends. Then there follows the sequence of _t__i_ distinct integers from 1 to _n_ — numbers of courses in random order, on which the _i_\-th depends. It is guaranteed that no course can depend on itself. It is guaranteed that the sum of all values _t__i_ doesn't exceed 105. ## Output Print _\-1_, if there is no the way to get a specialty. Otherwise, in the first line print the integer _m_ — the minimum number of online-courses which it is necessary to pass to get a specialty. In the second line print _m_ distinct integers — numbers of courses which it is necessary to pass in the chronological order of their passage. If there are several answers it is allowed to print any of them. [samples] ## Note In the first test firstly you can take courses number 1 and 2, after that you can take the course number 4, then you can take the course number 5, which is the main. After that you have to take only the course number 3, which is the last not passed main course.

现在你可以在贝尔兰国立大学修读在线课程！Polycarp 需要修完 #cf_span[k] 门他专业的主要在线课程才能获得学位。总共有 #cf_span[n] 门课程可供选择。情况因课程之间的依赖关系而变得复杂：每门课程都有一份必须在开始该课程之前修完的课程列表（列表可能为空，表示没有限制）。帮助 Polycarp 修完最少数量的课程以获得专业资格（即修完所有*主要*课程及必要的前置课程）。编写一个程序，输出课程的修读顺序。 Polycarp 依次修读课程，完成一门课程后才开始下一门。每门课程最多只能修读一次。第一行包含 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 105]）——在线课程的总数和 Polycarp 专业的主课程数量。第二行包含 #cf_span[k] 个互不相同的整数，范围从 #cf_span[1] 到 #cf_span[n]——Polycarp 专业的主在线课程编号。接下来 #cf_span[n] 行，每行描述一门课程：第 #cf_span[i] 行对应课程 #cf_span[i]。每行以整数 #cf_span[ti]（#cf_span[0 ≤ ti ≤ n - 1]）开头，表示该课程依赖的课程数量。接着是 #cf_span[ti] 个互不相同的整数（范围从 #cf_span[1] 到 #cf_span[n]），按任意顺序列出该课程所依赖的课程编号。保证没有课程依赖于自身。保证所有 #cf_span[ti] 的总和不超过 #cf_span[105]。如果无法获得专业资格，请输出 _-1_。否则，第一行输出整数 #cf_span[m]——获得专业资格所需修读的最少在线课程数量。第二行输出 #cf_span[m] 个互不相同的整数——按修读时间顺序列出必须修读的课程编号。如果有多个答案，输出任意一个即可。在第一个测试用例中，你可以先修课程 #cf_span[1] 和 #cf_span[2]，然后修课程 #cf_span[4]，接着修课程 #cf_span[5]（这是主课程）。之后你只需修课程 #cf_span[3]，这是最后一个未修的主课程。 ## Input 第一行包含 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 105]）——在线课程的总数和 Polycarp 专业的主课程数量。第二行包含 #cf_span[k] 个互不相同的整数，范围从 #cf_span[1] 到 #cf_span[n]——Polycarp 专业的主在线课程编号。接下来 #cf_span[n] 行，每行描述一门课程：第 #cf_span[i] 行对应课程 #cf_span[i]。每行以整数 #cf_span[ti]（#cf_span[0 ≤ ti ≤ n - 1]）开头，表示该课程依赖的课程数量。接着是 #cf_span[ti] 个互不相同的整数（范围从 #cf_span[1] 到 #cf_span[n]），按任意顺序列出该课程所依赖的课程编号。保证没有课程依赖于自身。保证所有 #cf_span[ti] 的总和不超过 #cf_span[105]。 ## Output 如果无法获得专业资格，请输出 _-1_。否则，第一行输出整数 #cf_span[m]——获得专业资格所需修读的最少在线课程数量。第二行输出 #cf_span[m] 个互不相同的整数——按修读时间顺序列出必须修读的课程编号。如果有多个答案，输出任意一个即可。 [samples] ## Note 在第一个测试用例中，你可以先修课程 #cf_span[1] 和 #cf_span[2]，然后修课程 #cf_span[4]，接着修课程 #cf_span[5]（这是主课程）。之后你只需修课程 #cf_span[3]，这是最后一个未修的主课程。

**Definitions** Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq k \leq n \leq 10^5 $. Let $ M \subseteq \{1, 2, \dots, n\} $ with $ |M| = k $ be the set of main courses. Let $ G = (V, E) $ be a directed graph where $ V = \{1, 2, \dots, n\} $, and for each course $ i \in V $, there are $ t_i $ prerequisite edges $ (p, i) \in E $ for each prerequisite $ p $ of course $ i $. **Constraints** 1. $ t_i \in \mathbb{Z}_{\geq 0} $, $ 0 \leq t_i \leq n-1 $, and the sum of all $ t_i \leq 10^5 $. 2. $ G $ is acyclic (guaranteed by problem). 3. Each course $ i \in V $ has distinct prerequisites from $ V \setminus \{i\} $. **Objective** Find the smallest subset $ S \subseteq V $ such that: - $ M \subseteq S $, - $ S $ is closed under prerequisites: if $ i \in S $, then all prerequisites of $ i $ are in $ S $. Then, output a topological ordering of $ S $ (any valid one). If no such $ S $ exists (i.e., cycle detected), output $-1$.

Samples

Input #1

Output #1

5
1 2 3 4 5

Input #2

Output #2

6
1 2 9 4 5 3

Input #3

Output #3

\-1

API Response (JSON)

{
  "problem": {
    "name": "C. Online Courses In BSU",
    "description": {
      "content": "Now you can take online courses in the Berland State University! Polycarp needs to pass _k_ **main** online courses of his specialty to get a diploma. In total _n_ courses are availiable for the passa",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF770C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Now you can take online courses in the Berland State University! Polycarp needs to pass _k_ **main** online courses of his specialty to get a diploma. In total _n_ courses are availiable for the passa...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "现在你可以在贝尔兰国立大学修读在线课程！Polycarp 需要修完 #cf_span[k] 门他专业的主要在线课程才能获得学位。总共有 #cf_span[n] 门课程可供选择。\n\n情况因课程之间的依赖关系而变得复杂：每门课程都有一份必须在开始该课程之前修完的课程列表（列表可能为空，表示没有限制）。\n\n帮助 Polycarp 修完最少数量的课程以获得专业资格（即修完所有*主要*课程及必要的前置课程）...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 10^5 $.  \nLet $ M \\subseteq \\{1, 2, \\dots, n\\} $ with $ |M| = k $ be the set of main courses.  \nLet $ G = (V, E) $ be a dire...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments