Background

  新的一年即将到来，祝同学们新年快乐！

Description

  2024年即将到来，我们有许多全新的愿望等待我们去实现。这些愿望就像一系列的目标，有些愿望需要在其他愿望实现后才能开始实现。

  假设你有一个新年愿望清单，一些愿望可能依赖于其他愿望的实现，我们可以将这些依赖关系表示为一个图，其中的节点表示愿望，有向边表示愿望之间的依赖关系。

  你的任务是，给定这个依赖关系图，编写一个程序来找出实现所有愿望的顺序。这个顺序需要满足每个愿望的所有依赖愿望都在它之前实现。

Format

Input

  第一行有两个正整数 $n, \space q$，$n$表示需要实现的愿望数量，$2≤n≤26$，第 $1$ 到 $n$ 个愿望将用大写的 $A,B,C,D,…$ 表示。$q$ 表示将给出的形如 $A<B$(愿望B依赖于愿望A的实现) 的关系的数量。

  接下来 $q$ 行每行输入 $3$ 个字符，分别为代表愿望的两个大写字母和一个<符号，表示两个愿望之间的依赖关系。

Output

  若根据前$x$个关系即可确定这$n$个愿望的顺序，输出x以及愿望的顺序；若根据前$x$个关系即发现存在矛盾，输出$x$和-1；若根据所有$q$个关系无法确定这$n$个愿望的实现顺序，输出-2。

Samples

4 1
B<D

-2

4 6
A<B
A<C
B<C
C<D
B<D
A<B

4
ABCD

4 6
A<B
B<A
B<C
C<D
B<D
A<B

-1
2

Limitation

  $2≤n≤26,1≤q≤600$。