3162 - 击鼓传花

题目描述

在一次班级联欢活动中,大家正在玩击鼓传花的游戏。

班里共有若干位同学,每位同学都有一个唯一的名字。 击鼓开始后,花会在同学之间不断传递。

活动开始前,老师制定了 N 条固定的传花规则:

i 条规则规定:

当名字为 S_i 的同学拿到花时,下一次一定会把花传给名字为 T_i 的同学。

所有规则同时生效,且满足:

  • 每个名字为 S_i 的同学 恰好有一条传花规则
  • 所有 S_i 两两不同。
  • 所有 T_i 两两不同。

花在游戏开始时,可以交到任意一位同学手中

如果击鼓游戏一直不叫停,那么花将会按照上述规则不断传递下去。 一旦花 无法继续传递,游戏就会结束,最后拿到花的同学需要表演节目

请你判断: 是否存在某种情况,使得花可以一直传递下去,游戏永远不会结束?

输入

1 行输入一个整数 N,表示有 N 条传递规则。

接下来 N 行,每行输入两个字符串 S_iT_i,表示第 i 条规则。

输出

如果存在一种传递过程,使得花可以一直传下去,输出 Yes,否则输出 No

样例

输入

2
b m
m d

输出

Yes

输入

4
alpha beta
beta gamma
gamma delta
delta epsilon

输出

Yes

输入

4
alpha beta
beta gamma
gamma alpha
delta epsilon

输出

No
说明

样例 1 说明

花传递的顺序为:b → m → d

无论花从谁开始,最终都会传到 d,之后无法继续传递,游戏结束。

数据范围

对于所有的测评数据,满足 1 \le N \le 10^5S_i, T_i 为长度不超过 8 的小写字母字符串,所有 S_i 两两不同,所有 T_i 两两不同。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 9
通过人数 7
金币数量 1 枚
难度 基础


上一题 下一题