12012. Заміна імен
Ви запускаєте веб-службу з \(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
Коментарі