Нэгэн улсын сан хөмрөг яагаад ч юм багассаар байв. Иймд ерөнхийлөгч нь сангийн яамандаа шинэ журам нэвтрүүлжээ. Шинэ журмын дагуу сангийн яамны ажилтан бүр өөрийн удирдлага дор ажиллах нэг хүнтэй хос болон ажиллах болсон(авилгаас урдчилан сэргийлэхийн тулд). Таны даалгавар бол өгөгдсөн сангийн яамны ажилтнуудын удирдлагын бүтцийг ашиглан уг шинэ журмаар хамгийн ихдээ хэдэн хос үүсч болохыг болон хамгийн их тооны хосуудыг хэдэн янзаар үүсгэж болохыг олох явдал юм.
Сангийн яамны сайд нь Б болно. Ажилтан бүр удирдлага доороо нэг ч ажилтангүй эсвэл хэд хэдэн ажилтантай байж болох ба харин өөрөө нэг л хүний (харин Б сангийн яам дотроо дээрээ удирдлагагүй ганц ажилтан нь байна) удирдлага дор ажиллана. Ажилтнуудын нийт тоо 1000-аас хэтрэхгүй. Зарим ажилтан ямар нэг хосын бүрэлдэхүүнд оролгүйгээр ганцаар үлдэж болно.

Input

Оролтын эхний мөрөнд ажилтнуудын нийт тоог илэрхийлэх N тоо байна (1<=N<=1000). Ажилтан бүр [1, N] завсраас авсан өөрийн гэсэн давтагдахгүй дугаартай байна. Сангийн сайдын (Б-ийн) дугаар 1 байна. Дараагийн N ширхэг мөр бүр нь нэг ажилтны тухай дараах мэдээллүүдийг зайгаар тусгаарлан агуулна: ажилтны дугаар, түүний удирдлага дор ажилладаг хүмүүсийн тоо K, эдгээр K ширхэг ажилтны дугаарууд. Оролтонд ямар нэг ажилтны тухай мэдээлэл үргэлж түүний даргын тухай мэдээллээс хойш байрлах болно.

Output

Гаралт нь хоёр мөрнөөс тогтоно. Эхний мөрөнд ажилтнуудын үүсгэж чадах хосуудын хамгийн их утга болох M бүхэл тоо байрлана. Дараагийн мөрөнд M хосыг ерөнхийлөгчийн журмаар үүсгэж болох бүх боломжийн тоо байна.
PS: Энэ улс нь Монгол улс биш болно

Example

Input:
7
1 3 2 4 7
2 1 3
4 1 6
3 0
7 1 5
5 0
6 0

Output:
3
4