33OJ
登录 注册

#D1050. 排序

排序

题目描述

给定 nn 个互不相同的大写字母(即前 nn 个大写字母)和 mm 条形如 X<YX<Y 的大小关系。这些关系按输入顺序给出。

你需要按顺序加入这些关系,并判断:

  1. 是否已经能唯一确定这 nn 个字母从小到大排列的顺序;
  2. 是否出现了矛盾,即同时存在 X<YX<Y 与 Y<XY<X;
  3. 如果都没有,继续加入下一条关系。

请求出最早能在第几条关系后确定顺序或发现矛盾,并输出对应的顺序或矛盾信息。

输入格式

第一行两个整数 n,mn,m。

接下来 mm 行,每行一个形如 X<Y 的关系,表示字母 XX 小于字母 YY。字母只会在前 nn 个大写字母中出现。

输出格式

输出一行,格式为以下三种之一:

  • 如果在第 xx 条关系后能唯一确定顺序,输出
    Sorted sequence determined after x relations: yyy...y.
    其中 yyy...y 是排好的字母序列;
  • 如果在第 xx 条关系后发现矛盾,输出
    Inconsistency found after x relations.;
  • 如果所有关系都无法确定顺序,输出
    Sorted sequence cannot be determined.。

样例

4 6
A<B
A<C
B<C
C<D
B<D
A<B
Sorted sequence determined after 4 relations: ABCD.
3 2
A<B
B<A
Inconsistency found after 2 relations.
26 1
A<Z
Sorted sequence cannot be determined.

样例解释

样例 1 中,处理到第 4 条关系 C<D 时,已经能推出 A<B<C<DA<B<C<D,顺序唯一;后面的关系不会再改变结果。

样例 2 中,前两条关系同时给出 A<BA<B 和 B<AB<A,出现矛盾,因此在第 2 条关系后输出矛盾。

样例 3 中,只有 A<ZA<Z 一条关系,其余 24 个字母之间没有足够信息,无法确定完整顺序。

数据范围与约定

子任务 分值 限制
11 3030 2≤n≤62 \le n \le 6,1≤m≤101 \le m \le 10
22 2≤n≤262 \le n \le 26,1≤m≤10001 \le m \le 1000,保证所有关系不产生矛盾
33 4040 2≤n≤262 \le n \le 26,1≤m≤10001 \le m \le 1000
  • 关系可能重复出现;重复关系不会改变已有信息;
  • 字母只会在前 nn 个大写字母中出现;
  • 子任务 2 的“保证所有关系不产生矛盾”是指:无论取前多少条关系,都不会同时推出 X<YX<Y 和 Y<XY<X。