12012. Заміна імен


Відправити розв'язок

Бали: 100
Time limit: 2.0s
Memory limit: 500M

Authors:
Problem type
Allowed languages
C++, Java, Pascal, Python

Ви запускаєте веб-службу з \(N\) користувачами. \(i\)-й користувач із поточним дескриптором \(S_i\) ​ хоче змінити його на \(T_i ​\) .

Тут \(S_1 ​ ,… S_N\) ​ попарно різні, а також \(T_1 ​ ,… T_N\) ​ .

Визначте, чи існує відповідний порядок зміни їхніх дескрипторів для виконання всіх їхніх запитів за таких умов:

  • ви змінюєте дескриптор лише одного користувача за раз;
  • ви змінюєте дескриптор кожного користувача лише один раз;
  • під час зміни дескриптора, новий дескриптор не повинен використовуватися іншими користувачами на цьому етапі.

Обмеження

  • \(1≤N≤10^5\)
  • \(S_i\) ​ і \(T_i\) ​ — це рядки довжиною від 1 до 8 (включно), які складаються з малих літер англійського алфавіту.
  • \(S_i ​ \neq T_i\) ​
  • \(S_i\) ​ попарно різні.
  • \(T_i\) є попарно різними.

Формат вхідних даних

Перший рядок містить ціле число \(N\).

Наступні  \(N\) рядків містять \(S_i, T_i\).

Формат вихідних даних

У вихідний потік виведіть відповідь: Yes або No.

Приклад вхідних даних

2
b m
m d

Приклад вихідних даних

Yes

1-й користувач із поточним дескриптором b хоче змінити його на m.

2-й користувач із поточним дескриптором m хоче змінити його на d.

Спочатку ви змінюєте дескриптор 2-го користувача з m на d; тоді ви змінюєте дескриптор 1-го користувача з b на m.

Таким чином ви зможете досягти мети. Зауважте, що ви не можете спочатку змінити дескриптор 1-го користувача на m, оскільки на цьому етапі його використовує 2-й користувач.

Приклад вхідних даних

3
a b
b c
c a

Приклад вихідних даних

No

1-й користувач із поточним дескриптором a хоче змінити його на b.

2-й користувач із поточним дескриптором b хоче змінити його на c.

3-й користувач із поточним дескриптором c хоче змінити його на a.

Ми не можемо змінити їхні ручки відповідно до умов.

Приклад вхідних даних

5
aaa bbb
yyy zzz
ccc ddd
xxx yyy
bbb ccc

Приклад вихідних даних

Yes

Коментарі

Ще немає коментарів.