В старой башне есть n тайных комнат, пронумерованных от 0 до n - 1. Изначально открыт только вход в комнату 0. Все остальные комнаты заперты.

В каждой комнате могут лежать ключи от некоторых других комнат. Если исследователь попадает в комнату, он может забрать все ключи, лежащие в ней, и затем использовать их, чтобы открыть соответствующие комнаты.

Для каждой комнаты i известен список комнат, ключи от которых находятся внутри неё. Требуется определить, можно ли, начиная из комнаты 0, в итоге получить доступ ко всем комнатам башни.

Входные данные

Первая строка содержит целое число n — количество комнат.

Далее следуют n строк. В i-й из них сначала записано целое число k_i — количество ключей в комнате i, а затем k_i целых чисел — номера комнат, от которых там лежат ключи.

Все данные подаются через стандартный ввод.

Выходные данные

Выведите true, если можно посетить все комнаты, начиная с комнаты 0, и false в противном случае.

Ответ выводится в стандартный вывод.

Ограничения

• 1 <= n <= 1000
• 0 <= k_i <= 1000
• 0 <= rooms[i][j] < n
• Суммарное количество ключей во всех комнатах не превосходит 3000

Примеры

Пример 1

Входные данные

2
1 1
0

Выходные данные

true

Пример 2

Входные данные

8
7 1 2 3 4 5 6 7
2 0 7
2 0 2
2 7 3
2 1 4
2 2 6
1 5
1 6

Выходные данные

true