题目内容

你正在参与一个大规模微服务架构的部署平台开发，系统中包含多个微服务，每个微服务在上线前需要其所有依赖的微服务都已部署并运行。

一个微服务通过字符串来表示，如：“$userservice$”，一个微服务可能依赖多个微服务的部署。

如果依赖关系存在环 （例如：$A$ 依赖 $B$，$B$ 依赖 $C$，$C$ 依赖 $A$），那么就无法部署，因为存在“循环依赖”。

请给出一个函数，判断给定的微服务依赖“无环”，并返回部署顺序，如果存在环，返回字符串 $Can$ $not$ $deploy$。

输入描述

• 第一行输入：$N$ 为参与部署的微服务的数量（$1 \le N \le 1000$，整数）
• 接下来接着 $N$ 行，每行描述一个服务的依赖关系（依赖关系是有向的，即 $A$ 依赖 $B$，表示 $B$ 要在 $A$ 之前部署，否则 $A$ 就会依赖失败）：
  • 格式：$serviceName1$ $M1$ $upstreamService1$ $upstreamService2$ $...$
  • 格式：$serviceName2$ $M2$ $upstreamService1$ $upstreamService2$ $...$
  • 格式：$serviceName3$ $M3$ $upstreamService1$ $upstreamService2$ $...$

$...$

• $serviceName$：微服务名称，名称不重复，每个微服务名称字符长度 $\le 100$ 个字符，字符包含 $26$ 个小写字母，数字 $0-9$。
• $M$：本行为微服务依赖的前驱服务数量，整数，$0 \le M \le 999$，当 $M=0$ 时，说明本微服务不依赖其他微服务。
• $upstreamService$：本行为微服务依赖的前驱服务名称。

注意：

1. 被依赖的前驱服务 $upstreamService$ 必须存在 $serviceName$ 中，且同一 $upstreamService$ 不重复。
2. 本行微服务不能依赖自己，即同一行的被依赖的前驱服务 $upstreamService$ 的值不等于本行的 $serviceName$。

输出描述

• 如果本微服务图无环，返回部署顺序，一行输出全部微服务名称，以空格隔开。 规则：

  $1$. 一个微服务部署时，它所依赖的前驱服务都已经部署。

  $2$. 如果存在多个前置依赖已经部署的微服务，输出时以微服务名称字符从小到大排序（即首字符 $ascii$ 码小的微服务排在前面，首字符相同的则比较下一个字符，依次类推）。

  $3$. 如果存在环，返回字符串 $Can$ $not$ $deploy$。

样例1

输入

3
aa 1 bb
bb 1 cc
cc 1 aa

输出

Can not deploy

说明

图中依赖存在环，故输出 $Can$ $not$ $deploy$。

样例2

输入

5
payment 2 auth order
order 1 user
auth 1 database
user 0
database 0

输出

database auth user order payment

说明

$1$.以拓扑排序顺序输出，当前 $database$ 和 $user$ 依赖的微服务均为 $0$，按照字符序优先输出 $database$

$2$.从拓扑网中删除 $database$ 及其入边，形成新图的 $auth$ 和 $user$ 依赖的微服务均为 $0$，按照字符序优先输出 $auth$

$3$.重复步骤1、2，最终顺序为 $database、auth、user、order、payment$